最优子结构原理和 dp 数组遍历方向 :: labuladong的算法小抄

[labuladong]

文章链接点这里：最优子结构原理和 dp 数组遍历方向

评论礼仪 见这里，违者直接拉黑。

[zxcvbnmleizhe]

2、遍历结束后，存储结果的那个位置必须已经被及算出来。计算，有个错别字

[labuladong]

感谢指出，已修复

[Maschinist-LZY]

1、遍历的过程中，所需的状态必须是已经计算出来的。

2、遍历结束后，存储结果的那个位置必须已经被计算出来。

下面来距离解释上面两个原则是什么意思。东哥，这里具体解释不小心打成距离了哦

[labuladong]

@Maschinist-LZY 谢谢指出，已修复~

[bert82503]

打卡，感谢！

[jennyliulfm]

感觉 现在在写遍历方向就好了。 在确定遍历方向之前 是不是需要最终的结果存在那个位置以及base case的位置 然后才能根据那两条rules 去确定遍历方向

[yokiizx]

斜着遍历没看懂....

[cillian-bao]

// 斜着遍历数组
for (int l = 2; l <= n; l++) {
    for (int i = 0; i <= n - l; i++) {
        int j = l + i - 1;
        // 计算 dp[i][j]
    }
}

斜着遍历数组这里是不是应该写为l=1开始，这样的画是正对角线，否则是正对角线上面一条斜线，不知道dong哥想表达的是那个

[labuladong]

@cillian-bao 理解你的意思，正对角线上的是 base case，所以我们进行状态转移是从正对角线上面一条开始

[billwhn]

显然，至少有两条路径：(i, j) -> #1 -> #4 和 (i, j) -> #3 -> #3。

第一种是不是写错了