このコードは 区間DP（Range DP） を用いた解法になっています。
以下のポイントに沿って、DPの状態定義・遷移・計算の流れ を詳しく解説します。
const dp = Array.from({ length: N }, () => Array(N).fill(0));dp[i][j]は、「ブロックの区間[i, j]だけが残っている状態のときに得られる最大得点」を表す。
各ステップで、今ある区間 [i, j] に対して、左端 i または右端 j にブロックを追加 する。
if (left > 0) {
const [P, A] = PA[left - 1]; // 左に追加するブロックのPとA
const score = left <= P - 1 && P - 1 <= right ? A : 0; // 得点を得られるかチェック
dp[left - 1][right] = Math.max(dp[left - 1][right], dp[left][right] + score);
}- 追加するブロックの
Pが区間[left, right]内にあるなら、得点Aを獲得できる。 dp[left - 1][right]を更新する。
if (right < N - 1) {
const [P, A] = PA[right + 1]; // 右に追加するブロックのPとA
const score = left <= P - 1 && P - 1 <= right ? A : 0; // 得点を得られるかチェック
dp[left][right + 1] = Math.max(dp[left][right + 1], dp[left][right] + score);
}- 追加するブロックの
Pが区間[left, right]内にあるなら、得点Aを獲得できる。 dp[left][right + 1]を更新する。
for (let width = 0; width < N; width++) {
for (let left = 0; left + width < N; left++) {
const right = left + width;- 区間
[i, j]のサイズを 1 から N まで順に広げる。 - 小さい区間から計算することで、大きい区間の
dp更新に使える。
console.log(dp[0][N - 1]);dp[0][N - 1]は すべてのブロックを使い切ったときの最大得点 なので、それを出力。
dp[i][j]の計算はO(1)（最大2回の更新）i, jのループがO(N^2)- 全体の計算量は
O(N^2)で十分高速
4
4 20
3 30
2 40
1 10
PA = [
(4, 20),
(3, 30),
(2, 40),
(1, 10)
]
| 区間 [i, j] | dp[i][j] | 得点の計算（どちらの端を追加するか） |
|---|---|---|
| [3,3] | 0 | 初期状態 |
| [2,3] | 10 | 右端に4を追加し、得点10 |
| [1,3] | 40 | 右端に3を追加し、得点40 |
| [0,3] | 60 | 右端に2を追加し、得点20 |
| [0,2] | 50 | 右端に3を追加し、得点30 |
| [0,1] | 30 | 右端に2を追加し、得点30 |
| [0,0] | 0 | 初期状態 |
dp[i][j]は区間[i, j]で得られる最大得点を表す- 左右の端を拡張する形で
dpを更新 - 計算順序を工夫し、O(N²) の高速な DP 解法が実現
このように、区間DPを用いることで、適切なスコア計算が可能になっています！ 🚀