DP 问题的思路？

LC刷了一大半，发现一些比较经典的DP问题，真的是在太难想出来了，有时候即使有思路，也十分难用一个简单的矩阵就到退出来。

（我所指的DP问题，是比较狭义的动态规划，比较经典的表示就是code中一定会有dp[]的出现....不是广义上的动态规划思想问题）

而且感觉每道题都挺独立的，很难做到举一反三，除非题A明显是题B的follow up(例如买卖股票）。

有朋友能分享一下对付这类的题目的心得吗？谢谢！
---------------------------------------------------
举个例子吧...LC的 Target Sum问题，
像DFS之类的答案，如 Shawngao 的 DFS 就相当易懂...
但是最高票的 Yuxiangmusic 的DP, 一开始的求Positive Subset Sum这部分都能理解到，但过了2 *Sum(P) == target + Sum(nums)这部分后,最后也是需要求有多少个元素Sum(P)的时候...DP那部分真的懵逼了..

所以想克服这些软肋..看来还是要靠题海战术..

find_advice 发表于 2017-5-28 08:26
跟递归没什么区别，反正一下子想不出来的就试试f(x)和f(x-1)f(x-2)...有啥关系

至于递归的话，可能Backtracking这part最近做得比较多，有时候画2,3层recursion call的结构立马能知道了。反而这种dp[]倒推的。 功力真的欠缺。而且我做DFS一般也是用recursion，脑子里的逻辑还是清楚的，dp这种太广的反而难推导。

跟递归没什么区别，反正一下子想不出来的就试试f(x)和f(x-1)f(x-2)...有啥关系

而且题目经常出现队列、阵列，每个格子都可以对应个结果

我经常是这样想的，对于一个特定的状态 dp[i][j] 他是由什么东西求出来的 找出source. 慢慢想总会想出来

find_advice 发表于 2017-5-28 08:28
而且题目经常出现队列、阵列，每个格子都可以对应个结果

如果是矩阵这种2维的反而可能会好，因为x轴和y轴的变化的规律可以慢慢倒推，最难的是一维的。 其实一开始我是做Target Sum,看到思路是转换为Partition Equal Subset Sum.....一下子就倒了。

topcoder有个tutorial专门讲dp的，不好意思，没有权限发链接。也有很多dp的题目，要是有时间可以找一些做一下，熟悉了就好了。

Target sum 其实就是背包问题 可以把背包问题的几种类型都弄懂 类似的很多题都能做了

来个简单的总结，有大概20道的dp可以总结为下面3中：
1. O(n) space 但是可以用O(1) space解决的， 大概就是横着的，梯子啊，sequence啊，栏杆/house啊
2. O(mn) space, 但是可以用O(min(m,n))来解决的，基本特征就是给了个m*n的矩阵
3. O(m+1 * n+1) space的，主要是string match类的，最典型的就是edit distance那个

剩下还有40道左右dp题还没做，或者还没有归类