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

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

为福贡等地区用户提供了全套网页设计制作服务，及福贡网站建设行业解决方案。主营业务为网站设计制作、成都网站制作、福贡网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

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

一动态规划问题的特征

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

1.2 最优子结构

1.3 贪心和动态规划的区别

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

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

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

一般的递归方法

优化：自顶向下带备忘

优化：自底向上

1.6 状态转移方程怎么写

一动态规划问题的特征

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

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

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
q=max(q,price[i]+recursion(price,searched,n-i));
}
（3）代码
recursion(vectorprice,vectorsearched, int n){
    if(searched[n]!=-1){     //如果之前已经记录了，就直接查表并返回
        return searched[n];
    }

    int q=INT_MIN;           //如果备忘没有记录，就按普通方法递归
    for(int i=1;i
（4）参数解释
n:输入规模，searched:一维数组的备忘录，i: i的范围表示规模为n的问题依赖的子问题的规模为1~n，i里面的操作表示依次对1~n规模的子问题的答案取大值。——即最优子结构。（复习：最优子结构：原问题的最优解由相关子问题的最优解组合而成。）（PS：我们写这段程序时是自顶向下的思路，所以我们假设答案已知。实际上，答案是递归的“归”的时候返回给上级函数的）q: 规模为n的原问题的最优解。
2.3 优化：自底向上1、模板
int n; //输入规模
(1)设置储存状态的数组，状态转移方程依赖多少维变量来转移，就设多少维的数组，vectordp(n+1);
(2)边界情况 dp[0]=……
(3)一般情况（规模从小到大）：
for(int i=0;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(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];
    }
三、状态转移方程怎么写（详见另一篇链接~）【C++】动态规划之状态转移方程（单串）_Bluepingu的博客-博客
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
            

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

            链接分享：http://bjjierui.cn/article/coihgi.html


    
        其他资讯
        
            
                    新手如何配置nodejs（服务器端的配置）-创新互联
                

                    IO流分析-创新互联
                

                    Java程序员需要掌握的英语词组-创新互联
                

                    怎么安装python解释器-创新互联
                

                    【计算机视觉】图像预处理-创新互联

定制建站费用3500元

品牌网站建设费用6000元

商城网站建设费用8000元

手机微信网站建站3000元

建站知识

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

其他资讯