求各位大佬 DP 类题目做法

算法课只学了 典型背包问题，但是看了看leetcode上的DP 感觉没什么规律可循啊，， 求各位大佬给些意见 或者学习资料

很多年前之前打过一段时间信息竞赛。动态规划问题是我当年最后一个搞懂的一个类别，学的慢是正常的，所以不要着急。我大概练了半年多才掌握。训练的方法大概就是筛选出这个类别的题目，然后不断地刷题。当然，不建议短时间内快速刷完，只是增加这类题的比例（比如每天1-3道），这样可以给大脑一点消化的时间。如果题目太难，建议先跳过；如果题目看似简单但仍然没有思路，可以研究一下题解（主要看如何表达状态）。题目用完之后，可以把之前的题目再刷一边，但是注意不要背具体的代码，只记思路。

我当年用的的 vijos，主要是因为界面好看（233），不过其他网站只要有题目分类应该也行。

至于解题思路，其实动态规划就是经过优化的递归，主要就是思考能不能通过规模小一点的问题的答案，推导出更大规模问题的答案。初学的时候，可以先写一写递归的写法。关于如何选择函数参数，一般是考虑哪个参数可以让问题的规模逐渐增大。比如背包问题，第一反映应该是复杂度跟背包大小有关，那这就可以作为一个参数。我们可以考虑往当前空间里随便放一个东西，然后把剩下的空间用最大价值的物品填满。后半句话是一个规模更小的一个同样的问题，于是我们就得到了递归表达式。然而这样遇到了一个问题，就是我们在填满剩下空间的时候，不能重复使用一个物品，而我们的参数中无法体现。解决这类问题的方法通常是增加一个参数，比如另一个参数限制每次只考虑前几个物品，就避免了重复问题。

其他的情况非常类似，比如遇到字符串/数组的问题，就考虑增加/减少一个字母/元素之后怎么办；如果有很多人，就考虑加一个人之后怎么办等等。这样相当于得到了 recursive case，最后加上 base case 就好了。

然后就是优化，首先我们可以把每次调用的结果记录到一个数组里，如果之前计算过就直接 return，避免重复计算。其次就是把递归改成循环：由于我们只会引用更小规模问题的结果，那么只要我们从小规模问题往大规模问题计算，就可以直接引用数组里的结果，而不需要函数调用。因为我们能保证那里是已经计算过的。还有 base case 的结果可以提前填到数组里。这样修改之后就是大家平时看到的答案。

我也正在练DP，粗浅的归了几类。
我的方法比较粗暴，就是针对常见题分类总结找套路，没有上升到DP思想的理解这种层次。
总结了几类：
第一类是矩阵上的路径那种，参加LC 62 63 那种，这种比较简单
第二类是一维度序列型，常见的如LC 300， 45， 55 这种，特点是一般是两个for，对于新的位置的dp[i], 要往回看这种
第三类是二维序列，基本上string上的dp多是这种，比如编辑距离，Longest common subsequence什么的，这种类型的有好多，但是套路相近，你确定了二维的框架后，再去找状态转移，至少有了思考方向了
第四类是背包
第五类是一维切分类，比如LC 132
看课程还说有啥博弈型，区间型什么的，我暂时没做到过。

https://www.geeksforgeeks.org/dynamic-programming/

我覺得搞懂這裏的20-30題已經差不多了，除非你遇見acm大神，那就祝你好運了😂😂

顶一下自己

大概有五六种dp套路吧，每个类型都刷几题熟悉下总结下什么题用什么方法。这样一般的dp题应该就没啥问题了

补充内容 (2019-7-4 10:44):
如果下次遇到同类型的题，读完题目还没看出是同一类型的dp / 还不知道往哪方面想，那证明这类dp你还没掌握, etc

根据自己之前的经验，想办法将每一步变化填在表格里面能够帮助你整理思路，反复练习就能轻松理解解题过程。理解了解题过程，代码就容易写了。写完代码后记得优化。

练习练习练习

一维 二维 区间

gregregre 发表于 2019-7-4 10:27
大概有五六种dp套路吧，每个类型都刷几题熟悉下总结下什么题用什么方法。这样一般的dp题应该就没啥问题了

...

所以是哪 5 6 种啊 ， 求大佬分享一点资料， 之前看新硅谷培训班 用数学归纳解决dp, 无奈没钱报班

KaWing 发表于 2019-7-4 11:36
https://www.geeksforgeeks.org/dynamic-programming/

我覺得搞懂這裏的20-30題已經差不多了，除非你遇見a ...

多谢大佬！！！