之前做过相关总结，但是没有今天二次看的时候这么深入https://blog.csdn.net/InNoVaion_yu/article/details/84892297

经过自己这两天的理解和实践后，个人再对动态规划、贪心、DFS、递归的关系再做一个总结；

首先，DFS和贪心、递归的关系：

DFS是一种遍历方式，而递归是程序的一种书写方式，贪心则是一种算法策略。

三者的关系可以总结为：贪心可以通过DFS来实现，而DFS可以通过递归来更简便的实现；

例如在经典的找零钱和算月饼问题，很简单的就是通过DFS来优先搜索一些满足条件的值，类似于深度遍历树的感觉；

而若是使用贪心算法，则每次DFS搜索，都先搜索值比较大的分支，从而使得局部最大变为整体最大；

值得一提：图论中的最短路径本质就是贪心，但是这个贪心得到的肯定是最优解，并且作者已经给出了证明；

其次：贪心和动态规划得关系：

两个压根就不是一个东西，是两种解题思想，只不过遍历结构相似；

最大的区别：贪心自上而下，未必是全局最优解；动态规划自下而上，肯定是全局最优解；

对于典型的暴力枚举和DFS来说，哪怕是DFS剪枝，都不可避免地产生一些重复计算，在无向图的遍历中也极为明显。所以动态规划自底向上来进行计算，先把子问题算出来，后续的所有计算都在先前的计算之上，类似于一层一层打地基建楼房。从而保证从底部找到的最优解必定会构成整体最优解；

而贪心算法未必，但是可以解决不少动态规划问题，但也只局限于OJ中。唯一例外的可能就是01背包问题，是没法用贪心算法解决的，这个后续再说。

但是尽管可以解决，也会造成TLE或者爆内存；原因还是贪心如果进行类DFS便利的时候，复杂度往往在m的n次方左右，其中m是选择情况，n为问题规模；

对于动态规划来说，最主要的就是建模，也就是怎么构建转换方程和dp数组，这个往往根据实际问题有关；

目前自己见到的题无非以下几种：字符串问题，序列问题，背包问题；

其中动态规划最难的有三个地方：

1.dp数组的建造；

2.dp数组边界的确定；

3.dp数组如何从边界向上构建；

对于字符串问题：

最长回文字串问题：

需要构建二维dp数组，其中dp[i][j]为布尔值，代表索引i-j构成的子串是否是回文串，在构建dp数组的时候进行统计；

其中状态转换方程为：当s[i]==s[j]相等时 dp[i][j]=0 (dp[i+1][j-1]=0)或者dp[i][j]=1 (dp[i+1][j-1]=1)

自己做的时候踩了一个坑，误把dp[i][j]=n，n代表i-j间回文子串长度，最后直接得到dp[0][s.size()-1]即为回文子串长度，但是这样是错误的；

 究其原因是对于asbbda来说，由于s和d不相等，所以相对dp值为0，尽管a和末尾a相等，但是也不能在其基础上+1变成1，因为中间不能构成回文子串；简而言之，只要中间不是回文子串，外部就不可能是回文子串；

最后难点也在于如何从边界向上构造，示例思想是通过字符长度区间来进行构造，也就是len=1、2、3的子串，遍历len的最大长度，使得dp[i][i+len]挨个进行构造；

https://www.cnblogs.com/songlinxuan/p/12355997.html

对于序列问题：

注意，序列中连续和不连续可能会导致dp数组的遍历有不同的理解；

1.不下降子序列问题：

典型的动态规划问题之一，主要是给出序列来找出最长的不下降序列。

之前用贪心做过相关的问题，从第一个开始找最接近自己的元素，挨个标记进行遍历，但是容易爆内存，并且复杂度奇高，最坏情况可能到达n*n次方。

如果用dp思想，则利用dp数组一次就可以遍历出来；

dp[i]代表以第i个元素结尾的序列。所以dp[i]可能出现两种情况，自己就是一个元素的序列，自己之前还有其他元素；

所以有状态转移方程：dp[i]=max(dp[j]+,1)，注意，其中j从1~i-1；

在进行状态转移的时候需要进行j的枚举。原因：3，4，1，2，5；当遍历到dp[5]的时候，前面有多个非递减序列，所以要进行枚举，来找到最长的路径；

https://www.cnblogs.com/songlinxuan/p/12355806.html

2.最大连续子序列和：

也是序列dp问题的典型题；

dp数组可以构建为dp[i]，当选择第i为作为连续序列中的最后一个元素。所以dp[i]=max(dp[i-1]+num[i],num[i])也就是两种情况：加上第i个数，反而小，还不如让这个数作为新序列的第一个元素；

所以一次遍历完之后，记录拆分路径，就可以一次得到多个最大序列，之后遍历找出最大的序列即可；

 https://www.cnblogs.com/songlinxuan/p/12355382.html   //这道题目记录路径的方式可以着重学一下，很有建设性；

总结：

其实总而言之，还是要想着怎么去划分子问题，最后是能找到所有的基础子问题——也就是dp边界，确立dp数组的机构；

其次，找到dp数组的构造方式后，要想怎么从递推边界向上推导；

动态规划（其一）字符串问题

原文：https://www.cnblogs.com/songlinxuan/p/12357431.html