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

如何定义原问题和子问题 f(n)，因为有时题目给的问题可能比较模糊，所以我们在求解时要经过一些转换。如何通过子问题 f(1), f(2), … f(n - 1)推导出原问题 f(n)，即如何写状态转移方程李煜东著《算法竞赛进阶指南》，摘录如下：：为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之，动态规划对状态空间的遍

Keroro军曹大人

4509人浏览 · 2022-12-24 13:43:02

Keroro军曹大人 · 2022-12-24 13:43:02 发布

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

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

一动态规划问题的特征

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

一动态规划问题的特征

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

1.1 重叠子问题

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

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

1.2 最优子结构

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

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

1.3 贪心和动态规划的区别

1、关于最优子结构

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

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

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

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

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

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

如何定义原问题和子问题 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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

2.1 一般的递归方法

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

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

各种长度的钢条能买多少钱的对照表

一般递归代码：

int re(int n)
{
	if(n==0)  //钢条长度为零的时候，返回零
		return 0;
	int q=N[n];
	int i;
	for(i=1;i<n;i++)  //遍历k~L-k每一种情况，找到里面的最大值，k为零时为不切割的情况，q=N[n]已经储存，不需要考虑
		q=maxx(q,r[i]+re(n-i));
	r[n]=q; //钢条长度为n时最多可以买到价格q
	return q;
}

2.2 优化：自顶向下带备忘

1、模板

(1)查备忘录，if(储存过) {直接返回结果}；

else{

(2)按一般方法递归得到结果。

(3)保存一般方法得到的结果

}

2、切割钢条解题思路

想象成钢条由切好的和没切好的两部分组成（左边切好了，右边没切好），对没切好的部分，可以递归地求解出它的大优价格。

（1）递归的层数和每层的规模

递归层数：[1,n]，钢条一共n段，可以在任意位置分成左边和右边，并且对右边递归。

每层规模：对于每层递归来说，如果上一层右边留下的长度是len，那么该层的可切割的规模是[1,len]，每层递归都要遍历这len种选择。

（2）状态转移方程

对于待切的长度（规模）为i的钢条来说，它的价值记为dp[len]（i取[1,len]），状态转移是对该层每段都尝试切割一下，取其中收益的最大值。如果切割，切割的部分记作左边，左边的价值是price[i]，并对右边递归，获得右边收益的最大值，是recursion(price,searched,n-i)。所以方程是：

for(int i=1;i<n;++i){

q=max(q,price[i]+recursion(price,searched,n-i));

}

（3）代码

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

    int q=INT_MIN;           //如果备忘没有记录，就按普通方法递归
    for(int i=1;i<n;++i){    //原问题依赖的子问题规模，不同问题不同
            q=max(q,price[i]+recursion(price,searched,n-i));//状态方程，不同问题不同
    }
    searched[n]=q;           //普通方法，保存结果
return q;
}

（4）参数解释

n:输入规模，searched:一维数组的备忘录，i: i的范围表示规模为n的问题依赖的子问题的规模为1~n，i里面的操作表示依次对1~n规模的子问题的答案取最大值。——即最优子结构。（复习：最优子结构：原问题的最优解由相关子问题的最优解组合而成。）（PS：我们写这段程序时是自顶向下的思路，所以我们假设答案已知。实际上，答案是递归的“归”的时候返回给上级函数的）q: 规模为n的原问题的最优解。

2.3 优化：自底向上

1、模板

int n; //输入规模

(1)设置储存状态的数组，状态转移方程依赖多少维变量来转移，就设多少维的数组，vector<int> dp(n+1);

(2)边界情况 dp[0]=……

(3)一般情况（规模从小到大）：

for(int i=0;i<n;++i){

dp[i]=……

}

自底向上的方法的思路详解：

（1）规模从小到大

规模的从小到大及其状态转移方程，很多时候要用脑子想象，因为题目给出的规模是n不是1啊~~~我们这么想象：假设规模（这里是钢条的长度）为0会怎样？规模为1会怎样？规模为2会怎样？规模为2的结果怎么从规模为1的结果中转移过来？

比如这题规模为2的钢条可以左边切割1，右边剩下规模为1的钢条（自底向下的思路里，可以把右边的理解成已经处理过的钢条），也就是说右边已经处理好的规模为1的钢条，加上1的长度就是规模为2的钢条，规模为1的钢条的价值，加上左边钢条的价值，就是规模为2的钢条的价值啦~。同理规模为3的钢条的价值，可以是右边规模为1的钢条的价值+左边切割2的钢条的价值得来，也可以是右边规模为2的钢条的价值+左边切割1的钢条的价值得来，那究竟选哪一个呢？当然是选收益大的啦~。

（2）状态转移方程

自底向下的状态通，c++常用数组保存，我选择用STL的动态数组vector

设规模为i的钢条的价值为dp[i],状态转移方程：

dp[0]=0;//边界条件，钢条长度为0，收益为0

dp[i]=max(dp[i],dp[i-j]+price[i]);//一般情况

    int CutBar(vector<int> price, int n) {
        vector<int> dp(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];
    }