部分列《DP・漸化式》

DPメニュー【最長増加部分列・最長減少部分列】

問題【STEP: 1】最長増加部分列
Task
n 本の木を高さが単調増加になるように伐採したとき 残る木の最大値は?

【最長増加部分列】コード

reader.on('close', () => {
   const n = Number(lines[0]);
   const a = [];  // 木の高さ
   for (let i = 1; i <= n; i++) {
      a.push(Number(lines[i]));
   }
   const dp = [1];  // dp[k] は a[0] ~ a[k] 間の 最長増加部分列の長さ
   for (let i = 1; i < n; i++) {  // 1 <= (i < n)
      dp.push(1);  // 部分増加列の要素が a[i]のみの場合は dp[i] は 1
      for (j = 0; j < i; j++) {  // 0 <= j < i
         if (a[j] < a[i]) {  // a[j]が a[i]より小さければ…
         dp[i] = Math.max(dp[i], dp[j] + 1);
 // a[0] ~ a[i] 間の 増加部分列の長さは dp[j] + 1 と dp[i] のうち 長い方 で更新
      }
    }
  }
  console.log(Math.max(...dp));
});
hogeちゃんの画像

問題文の疑似コードを見ながらコーディングしましたが 聞きなれない用語が多くって タイヘン。

top
問題【FINAL】最長減少部分列
Task
n 本の木を高さが単調減少になるように伐採したとき 残る木の最大値は?

【最長減少部分列】コード

reader.on('close', () => {
   const n = Number(lines[0]);
   const a = [];  // 木の高さ
   for (let i = 1; i <= n; i++) {
      a.push(Number(lines[i]));
   }
   const dp = [1];  // dp[k] は a[0] ~ a[k] 間の 最長増加部分列の長さ
   for (let i = 1; i < n; i++) {  // 1 <= (i < n)
      dp.push(1);  // 部分増加列の要素が a[i]のみの場合は dp[i] は 1
      for (j = 0; j < i; j++) {  // 0 <= j < i
         if (a[j] > a[i]) {  // a[j]が a[i]より大きければ…
         dp[i] = Math.max(dp[i], dp[j] + 1);
 // a[0] ~ a[i] 間の 減少部分列の長さは dp[j] + 1 と dp[i] のうち 長い方 で更新
      }
    }
  }
  console.log(Math.max(...dp));
});
hogeちゃんの画像

増加が減少に変わっただけなので if文の条件式がa[j] > a[i]になりました。

top

コメント