关于动态规划【力扣516.最长回文子序列的想法】

1、动规五部曲

（本题是代码随想录关于动态规划的最后一道题目，所以回看一下动态规划的操作）

第一步：dp数组本身的含义

第二步：递推关系

第三步：dp数组初始化

第四步：遍历顺序

第五步：打印dp数组（用于debug）

2、【dp数组本身的含义】

大部分时候，dp数组本身的含义都是通过题目的问题来确定的。

// 例如本题问的是最长子序列长度，那dp数组本身的含义就是从i到j的最长子序列长度为dp[i][j]

但是也有特殊情况

// 比如上一题（力扣647.回文字串）是根据题目的主语：回文字串的定义来确定。回文字串的定义是从前往后读和从后往前读是一样的，即从中间开始左右两边是对称的。

【我的总结】dp数组本身的含义优先用题目的问题，其次用题目的主语

（如果用题目的问题作为“dp数组本身的含义”不好找递推关系再用题目的主语）

3、【递推关系】

递推关系就要根据实际情况、脚踏实地、一步一步的具体分析

// 比如这题，就要分析头和尾相同的话，状态从哪里转移过来；不同的话，状态可能从哪里过来，如果可能从几个地方过来，那取最大值还是取最小值。每一步的分析都要切合题目实际要求

【我的总结】要找递推关系，具体问题具体分析

4、【dp数组初始化】

在初始化dp数组之前，我们要先把递推关系思考出来，然后看一下递推关系的根在哪里。

就是递推关系必须要有一个什么起源，最开始需要什么东西，才可以一直往外推

// 比如本题，递推公式一直回去。i和j会一直往中间移动，递推公式一直回去，最后都会回到i和j相等的时候。

（例1，如下图所示）

// 溯源后，找到递推关系的最开始的起源地

（例2，如下图所示）

// 溯源后，找到递推关系的最开始的起源地

// 所以说i=j的地方就是发源地

所以本题的dp数组初始化如下图所示

【我的总结】要初始化什么根据递推关系的根来确定

5、【遍历顺序】

动态规划的题目都是有一个很明显的状态转移的，所以可以利用状态转移的方向，

也就是递推关系的推导方向来判断遍历顺序

（这就是为什么在动规五部曲里，递推关系的思考在dp数组初始化和遍历顺序之前）

（同样的最后面返回值的确定也跟递推关系有关系）

例如本题的递推关系的推导方向如下图所示（借用代码随想录的图）

要计算出dp[i][j]需要先有左、左下、下三个地方的值，所以遍历顺序从最后一行开始遍历，从下往上，从左往右。

【我的总结】遍历顺序根据递推关系的推导方向来确定

6、【返回值】

就是代码的最后一个部分，return ......

// 这部分也根据递推关系判断

// 有的要用dp数组左下角，有的要用dp数组右下角，有的要用dp数组右上角，有的要用dp数组里的最大值

// 同样的，去看递推关系的推导方向，看一下一直往后推会去哪里

// 比如本题的递推关系就会一直推向右上角，那么返回值就在dp数组的右上角

// 所以返回dp[0][s.size()-1];

【我的总结】返回什么看递推关系

7、【我的疑问】 递推关系为什么不是dp[i-1][j+1]+2？

因为dp[i-1][j+1]表示的是更大的外部区间