动态规划的技巧
以下是我的个人刷题经验，请大家谨慎采纳，如有疑问或认为不对的，欢迎评论和讨论。
1. 在dp里使用辅助位置
有时候边界条件要特殊考虑，比较麻烦，为了简化对边界条件的处理，可以适当增加辅助位置。
1. 1. 相关题目
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. 相关题目
题目
返回将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. 相关题目
题目是要求能获得硬币的最大数量，根据上面的”题目给的问题，一般就是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上大概率也会超时。
原文地址：https://blog.csdn.net/liushuidehao/article/details/142700800
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！