今回は paiza のDPで「【部分列】最長減少部分列」の問題に挑戦！
前回の最長部分増加列が解ければ、これも解けるはず！
問題概要
◯入力
- 1行目：整数 N（数列の長さ）
- 2行目以降：長さ N の整数列 a₁, a₂, …, aₙ
◯出力
- 数列 a の中から取り出せる 単調減少部分列（a_{k_1} > a_{k_2} > … > a_{k_m}） の最長の長さを求める。
入力例：
5
109
110
108
103
100
出力例：
4
✅ OK例：
const rl = require('readline').createInterface({ input:process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const n = Number(lines[0]);
const a = lines.slice(1).map(Number);
a.unshift(0);
const dp = [];
dp[1] = 1;
for(let i = 2; i <= n; i++){
dp[i] = 1;
for(let j = 1; j < i; j++){
if(a[j] > a[i]){
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
console.log(Math.max(...dp.slice(1)));
});
-
dp[i]= 「木 i を最後に選んだときに残せる木の最大本数」
- 初期値はすべて
1（どの木も1本だけ残せる）
- 漸化式は
if (a[j] > a[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
→ 木 i の高さが木 j より低ければ、j の後に i を続けられるので更新する。
処理の流れ
配列にする（1-indexにしてるので先頭に0を挿入）
a = [0, 109, 110, 108, 103, 100]
🔍 DP更新の流れ（入力例：109, 110, 108, 103, 100）
- i=1, a[1]=109
- 初期値 → dp[1] = 1
- i=2, a[2]=110
-
a[1]=109 < 110 → 条件に合わない
→ dp[2] = 1
-
- i=3, a[3]=108
-
a[1]=109 > 108 → 候補: dp[1]+1 = 2
-
a[2]=110 > 108 → 候補: dp[2]+1 = 2
→ dp[3] = 2
-
- i=4, a[4]=103
-
a[1]=109 > 103 → 候補: dp[1]+1 = 2
-
a[2]=110 > 103 → 候補: dp[2]+1 = 2
-
a[3]=108 > 103 → 候補: dp[3]+1 = 3
→ dp[4] = 3
-
- i=5, a[5]=100
-
a[1]=109 > 100 → 候補: dp[1]+1 = 2
-
a[2]=110 > 100 → 候補: dp[2]+1 = 2
-
a[3]=108 > 100 → 候補: dp[3]+1 = 3
-
a[4]=103 > 100 → 候補: dp[4]+1 = 4
→ dp[5] = 4
-
DP結果
dp = [ -, 1, 1, 2, 3, 4 ]
最大値は 4
つまり「109 → 108 → 103 → 100」というように4本残せるということ！
🗒️ まとめ
👉 この問題は「LIS（最長増加部分列）」の逆バージョン（大小比較を逆にするだけ）と考えると理解しやすい！