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

[labuladong]

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

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

[zxcvbnmleizhe]

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

[labuladong]

感谢指出，已修复

[Maschinist-LZY]

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

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

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

[labuladong]

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

[bert82503]

打卡，感谢！

[jennyliulfm]

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

[twotwoba]

斜着遍历没看懂....

[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。

第一种是不是写错了

[labuladong]

感谢指出，我改下

[yonggui-yan]

滴滴滴打卡

[marcmk6]

bool dp(string& s, int i, string& p, int j) {
    dp(s, i, p, j + 2);     // #1
    dp(s, i + 1, p, j);     // #2
    dp(s, i + 1, p, j + 1); // #3
}

关于判断正则表达式的暴力解法是否存在重叠子问题有些困惑。

假设当前进入dp函数时参数是(i, j)，那么根据函数逻辑，要么会执行return dp(s, i, p, j + 2) || dp(s, i + 1, p, j); (也就是1和2号递归调用)，要么执行return dp(s, i, p, j + 2); (也就是3号递归调用)。
或者说因为(i, j)是固定的，那么从这个状态到调用(i+2, j+2)只能固定是(i, j) -> #1 -> #2 -> #2和(i, j) -> #3 -> #3两种中的一种路径，但文章意思似乎是#1+#2和#3都会在dp(i, j)中被调用。

不知道我这样理解是哪里有问题。

[marcmk6]

重叠子问题的产生似乎与.*有关
如用例s="aabcbcbcaccbcaabc" p=".*a*aa*.*b*.c*.*a*"会重复计算

ccbcaabc@a*
abc@a*
bc@a*

[labuladong]

两种中的一种路径

这句话说的不对。暴力穷举会遍历整棵递归树，这些重复的路径都会被遍历，也就产生了冗余计算

[rekkles0905]

怎么感觉阅读顺序有点乱。。是从上往下读么，还是跟着超链接跳着读，抑或自己凭感觉选着读 :-)

[CarlLy7]

看完这篇文章了，总是每次看东哥的时候收到面试通知，这次也是正在看着收到了面试通知，所以看的水过地皮湿了，明天过来二刷，简单说一下看完之后的一个小总结吧，关于dp遍历方向的问题，东哥说的两个核心已经很好了，我再说一下我自己的一个小技巧，首先你要看当前这个位置的结果是从那几个方向过来的，比如如果是左上、左、上这三个方向来的我们其实就可以从上到下，从左到右，因为有从左上来的。如果是从左下、下、左这三个方向来的，因为有左下所以我们可以从下往上从左往右进行一个遍历。

东哥总结的很好了，我只是总结一下我自己的一个小技巧。

[CarlLy7]

求助东哥，一直看东哥的动态规划也看了一些文章了，自顶向下的递归方法现在用的还算可以，但是自底向上的迭代解法还是不能用的得心应手，应该咋办啊

[lemonzeng]

斜着遍历不太能懂，不知道有没有相关的题目

[hanglearning]

东哥好，我想确认一个问题。文章说

这篇文章就给你讲明白以下几个问题：
2、如何判断一个问题是动态规划问题，即如何看出是否存在重叠子问题。

对于这句话，我的理解是重叠子问题是动态规划问题的一个特性，也就是说必须存在重叠子问题才有可能是动态规划。可是下面又写

找最优子结构的过程，其实就是证明状态转移方程正确性的过程，方程符合最优子结构就可以写暴力解了，写出暴力解就可以看出有没有重叠子问题了，有则优化，无则 OK。这也是套路，经常刷题的读者应该能体会。

想确认这里的“无则OK”，是指看不出来ok，还是指没有重叠子问题也ok？如果是没有重叠子问题也ok，那这样写出的解法（虽然用到状态转移方程的思维），是不是就不算动态规划了？

感谢解答！