1、动规五部曲本题是代码随想录关于动态规划的最后一道题目所以回看一下动态规划的操作第一步dp数组本身的含义第二步递推关系第三步dp数组初始化第四步遍历顺序第五步打印dp数组用于debug2、【dp数组本身的含义】大部分时候dp数组本身的含义都是通过题目的问题来确定的。// 例如本题问的是最长子序列长度那dp数组本身的含义就是从i到j的最长子序列长度为dp[i][j]但是也有特殊情况// 比如上一题力扣647.回文字串是根据题目的主语回文字串的定义来确定。回文字串的定义是从前往后读和从后往前读是一样的即从中间开始左右两边是对称的。【我的总结】dp数组本身的含义优先用题目的问题其次用题目的主语如果用题目的问题作为“dp数组本身的含义”不好找递推关系再用题目的主语3、【递推关系】递推关系就要根据实际情况、脚踏实地、一步一步的具体分析// 比如这题就要分析头和尾相同的话状态从哪里转移过来不同的话状态可能从哪里过来如果可能从几个地方过来那取最大值还是取最小值。每一步的分析都要切合题目实际要求【我的总结】要找递推关系具体问题具体分析4、【dp数组初始化】在初始化dp数组之前我们要先把递推关系思考出来然后看一下递推关系的根在哪里。就是递推关系必须要有一个什么起源最开始需要什么东西才可以一直往外推// 比如本题递推公式一直回去。i和j会一直往中间移动递推公式一直回去最后都会回到i和j相等的时候。例1如下图所示// 溯源后找到递推关系的最开始的起源地例2如下图所示// 溯源后找到递推关系的最开始的起源地// 所以说ij的地方就是发源地所以本题的dp数组初始化如下图所示【我的总结】要初始化什么根据递推关系的根来确定5、【遍历顺序】动态规划的题目都是有一个很明显的状态转移的所以可以利用状态转移的方向也就是递推关系的推导方向来判断遍历顺序这就是为什么在动规五部曲里递推关系的思考在dp数组初始化和遍历顺序之前同样的最后面返回值的确定也跟递推关系有关系例如本题的递推关系的推导方向如下图所示借用代码随想录的图要计算出dp[i][j]需要先有左、左下、下三个地方的值所以遍历顺序从最后一行开始遍历从下往上从左往右。【我的总结】遍历顺序根据递推关系的推导方向来确定6、【返回值】就是代码的最后一个部分return ......// 这部分也根据递推关系判断// 有的要用dp数组左下角有的要用dp数组右下角有的要用dp数组右上角有的要用dp数组里的最大值// 同样的去看递推关系的推导方向看一下一直往后推会去哪里// 比如本题的递推关系就会一直推向右上角那么返回值就在dp数组的右上角// 所以返回dp[0][s.size()-1];【我的总结】返回什么看递推关系7、【我的疑问】 递推关系为什么不是dp[i-1][j1]2因为dp[i-1][j1]表示的是更大的外部区间