动态规划的技巧

以下是我的个人刷题经验，请大家谨慎采纳，如有疑问或认为不对的，欢迎评论和讨论。

1. 在dp里使用辅助位置

有时候边界条件要特殊考虑，比较麻烦，为了简化对边界条件的处理，可以适当增加辅助位置。

1. 1. 相关题目

72. 编辑距离：

dp[i][j]表示word1的0~i位到word2的0~j位的最小编辑距离，则dp[i][j]与dp的[i-1]和[j-1]相关。

当i或j等于0的时候，就需要特殊处理，不然[i-1]或[j-1]就数组越界了（小于0）。

考虑在word1和word2前加一个空白字符，然后人为规定（当然要具体推断一下）这个空白字符位置的具体dp值，就可以统一用dp[i][j]与dp的[i-1]和[j-1]相关来递推了。

2. 猜到填充dp数组的方向

考察dp相关的暴力递归最后返回时行列的值，就可以猜到dp的迭代方向是从左到右还是从右到左，从上到下还是从下到上。

dp相关的暴力递归，一般会有形如func(i,j,p1,p2...)的递归函数，而调用该递归的主函数，最后返回的一般是这种递归函数的结果。

比如：

main(){
    // ......各种代码
    return func(a.len()-1, b.len()-1);
}

那dp大概率就是i从0到a.len()、j从0到b.len()来填满。

再如：

main(){
    // ......各种代码
    return func(0, b.len()-1);
}

那dp大概率就是i从a.len() 到0、j从0到b.len()来填满。

为啥会有这个经验？因为最后返回的dp结果，一定是”最后“得到的，那它的反方向，就是最先”开始“的，从”开始“到”结果“，就知道方向了。

注意：

动态规划的返回值一般有两种形式，返回某种数量、返回某种列表。

3. 题目给的问题，一般就是dp的含义

因为题目给的问题，就是没有后效性的，不然答案就不是确定的（不同的解题方法有不同的答案）。

注意，题目一般不会把dp各个维度的定义给出来，只是一个方向性的定义。

3.1. 相关题目

72. 编辑距离

题目

返回将word1转换成word2所使用的最少操作数

dp的设计

从word1到word2，那就是2维dp了，直接设dp[i][j]就是“word1的i转换成word2的j所使用的最少操作数”，至于“word1的i”代表什么？就需要再想一想。很自然想到3个方向：

word1的第i位：word1[i]
word1的前i位：word1[0]~word1[i]
word1的后i位：word1[i]~word1[len-1]

很容易排除掉1、3两种情况，那就是2了，最终题解也是用的2

4. 想办法隔离后效性

4.1. 相关题目

312.戳气球

题目是要求能获得硬币的最大数量，根据上面的”题目给的问题，一般就是dp的含义“这个经验，可以有以下几种候选的dp定义思路：

前i个球爆完后，再爆剩下的球，所能得到的最大数量
后i个球爆完后，再爆剩下的球，所能得到的最大数量
第i个球是第一个爆的球的情况下，所能得到的最大数量
第i个球是最后一个爆的球的情况下，所能得到的最大数量

所有思路都涉及到某个球爆了后，把区间分成左右两边，但左边的爆炸会影响到右边，比如下图所示的5个球

球的值	11	12	13	14	15
球的序号i	1	2	3	4	5

序号i=3爆了，区域分成左（1、2）和右（4、5）两块：左边的1先爆，右边4、5爆的时候最多乘以一个左边界的2；如果左边的2先爆，右边4、5爆的时候最多乘以的就是左边界的1了。

除非左右边界搁一个不会爆的东西，让它把两边隔离开来，两边的边界都不会超过它，左右边界就不会互相影响了。

考察上文的4个思路，只有第4个具有这种隔离的特点，所以最终用4作为dp的定义思路。

5. dp数组的大小一般不会超过3维

如果自己想到的dp超过了3维（一般是通过暴力优化到dp的时候出现的），那大概率思路错了，就算好不容易写出来，在leetcode上大概率也会超时。