【动态规划】最强最详细的思路及模板（C++）-创新互联

本文根据力扣动态规划精讲（一）（二）（三）的框架编写。

动态规划精讲（一） - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

目录

一 动态规划问题的特征

1.1 重叠子问题：子问题反复出现（递归树可以很清晰地看出）

1.2 最优子结构

1.3 贪心和动态规划的区别

1.4 无后效性：如何恰当定义问题

最优化问题-动态规划中有两个难点：

1.5 模板大框架（自顶向下，自底向上）

一般的递归方法

优化：自顶向下带备忘

优化：自底向上

1.6 状态转移方程怎么写

1. 动态规划思想用来求解的是最优化问题。
2. 原问题可以用包括子问题的递归式来描述。
3. 最优子结构：原问题的最优解可以且必须由子问题的最优解得到。
4. 重叠子问题：某些子问题在求解过程中反复出现，导致大量重复计算，所以要用①记忆化搜索（自顶向下的带备忘的方法）（普通递归的优化版本）②自底向上的方法

重叠子问题：某些子问题在求解过程中反复出现，导致大量重复计算，所以要用①记忆化搜索（自顶向下的带备忘的方法）（普通递归的优化版本）②自底向上的方法 

例子：切割钢条的递归树（详见2）

回顾下动态规划解决的是什么类型的问题？——最优化问题（optimization problem），那么最有子结构说的是：原问题的最优解由相关子问题的最优解组合而成。

并且这些子问题可以独立求解。并且原问题的最优解，一定要在子问题求出最优解之后，才由子问题的最优解“递归转移”（某些地方也叫“组合”，anyway这个动词用的比较模糊）而求出来。

1、关于最优子结构

贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解无需记录
动态规划：全局最优解中一定包含某个局部最优解，但不一定包含上一步的局部最优解，因此需要记录之前的所有的局部最优解
2、关于子问题最优解组合成原问题最优解的组合方式

贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可，这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况，于是构不成一棵完整的树
动态规划：动态规划需要对每一个子树求最优解，直至下面的每一个叶子的值，最后得到一棵完整的树，在所有子树都得到最优解后，将他们组合成答案
3、结果正确性

贪心不能保证求得的最后解是最佳的，复杂度低
动态规划本质是穷举法，可以保证结果是最佳的，复杂度高

作者：FennelDumplings
链接：https://leetcode.cn/leetbook/read/dynamic-programming-1-plus/xcrktd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

最优化问题-动态规划中有两个难点：

• 如何定义原问题和子问题 f(n)，因为有时题目给的问题可能比较模糊，所以我们在求解时要经过一些转换。
• 如何通过子问题 f(1), f(2), … f(n - 1)推导出原问题 f(n)，即如何写状态转移方程

李煜东著《算法竞赛进阶指南》，摘录如下：：

为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的「状态」，图中的边则对应状态之间的「转移」，转移的选取就是动态规划中的「决策」。

我的解释：

「有向无环图」「拓扑序」表示了每一个子问题只求解一次，以后求解问题的过程不会修改以前求解的子问题的结果；
换句话说：如果之前的阶段求解的子问题的结果包含了一些不确定的信息，导致了后面的阶段求解的子问题无法得到，或者很难得到，这叫「有后效性」，我们在当前这个问题第 1 次拆分的子问题就是「有后效性」的（大家可以再翻到上面再看看）；
解决「有后效性」的办法是固定住需要分类讨论的地方，记录下更多的结果。在代码层面上表现为：
状态数组增加维度，例如：「力扣」的股票系列问题；
把状态定义得更细致、准确，例如：前天推送的第 124 题：状态定义只解决路径来自左右子树的其中一个子树。

作者：liweiwei1419
链接：https://leetcode.cn/problems/maximum-subarray/solution/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

例子：《算法导论》P205切割钢条

给你一根钢条，你可以把它切成几个小部分（也可以不用切割），要找到一种方法，使得这根钢条可以卖出最多的价钱。

一般递归代码：

int re(int n)
{
	if(n==0)  //钢条长度为零的时候，返回零
		return 0;
	int q=N[n];
	int i;
	for(i=1;i

recursion(vectorprice,vectorsearched, int n){
    if(searched[n]!=-1){     //如果之前已经记录了，就直接查表并返回
        return searched[n];
    }

    int q=INT_MIN;           //如果备忘没有记录，就按普通方法递归
    for(int i=1;i

int CutBar(vectorprice, int n) {
        vectordp(n+1);
        dp[0] = 0;
        for (int i = 1; i<= n; i++) {//钢条规模
            for (int j = 1; j<=i; ++j) {//在该规模下，依次记录切下长度为j的钢条的收益，取其中的大值，最少切1，所以j=1
                dp[i] = max(dp[i], dp[i - j] + price[j]);
            }
        }
        return dp[n];
    }