求各位大佬 DP 类题目做法

我的理解，首先要认识到动态规划（迭代），包括备忘录法（递归方式的动态规划），其核心用意非常明确，就是避免子问题（大问题划分成若干的小问题）的多次重复计算，故利用空间（如数组，或map）将子问题的结果记录下来。所以求解包括辨别动态规划问题的核心就是，在你构思题目解法的时候，有没有发现需要多次求解的重复子问题。
当发现了重复子问题，就需要应用动态规划思想求解。抽象看来，常见的套路是，根据能确定子问题的变量的个数作为动态规划数组的维度，通过递归和迭代将子问题求解，后续重复求解的时候只需要查找dp数组或者map即可。
具体而言，多练多写。

這兩個影片整理得挺不錯，樓主可以參考參考：

https://www.youtube.com/watch?v= ... Q1v0AjX&index=9
https://www.youtube.com/watch?v= ... Q1v0AjX&index=8

DP问题的本质是，把一个大问题分解成几个小步骤，这几个前面的state会影响此刻的state

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

tianjiayangmike 发表于 2019-9-20 15:05
我也正在练DP，粗浅的归了几类。
我的方法比较粗暴，就是针对常见题分类总结找套路，没有上升到DP思想的理 ...

兄台 你的归类 不对  看看崔添翼大佬的背包九讲 吧  
你的分类 太初级了 没看透问题的本质呢
https://github.com/tianyicui/pack
还有 oi-wki上的 其他类型的dp总结

yanjinbin 发表于 2019-9-20 15:23
兄台 你的归类 不对  看看崔添翼大佬的背包九讲 吧  
你的分类 太初级了 没看透问题的本质呢
https:// ...

感谢老哥指点，我刚开始搞DP题，理解的确实很浅，我明天好好钻研一下你给的资料

tianjiayangmike 发表于 2019-9-20 16:18
感谢老哥指点，我刚开始搞DP题，理解的确实很浅，我明天好好钻研一下你给的资料

哈哈  我也是 自己刷了背包九讲 发现这类型的问题  可以吃透了
  就是类似 我一定可以自己写出来 有理论指导的含义在
当然 细节上面还是需要自己 多刷刷  

linear scan回头看？谁来给我解释一下这句话是什么意思

看起来不错，各位大佬分享各种方法