【动态规划】最强最详细的思路及模板(C++)-创新互联
本文根据力扣动态规划精讲(一)(二)(三)的框架编写。
为福贡等地区用户提供了全套网页设计制作服务,及福贡网站建设行业解决方案。主营业务为网站设计制作、成都网站制作、福贡网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!动态规划精讲(一) - LeetBook - 力扣(LeetCode)全球极客挚爱的技术成长平台
目录
一 动态规划问题的特征
1.1 重叠子问题:子问题反复出现(递归树可以很清晰地看出)
1.2 最优子结构
1.3 贪心和动态规划的区别
1.4 无后效性:如何恰当定义问题
最优化问题-动态规划中有两个难点:
1.5 模板大框架(自顶向下,自底向上)
一般的递归方法
优化:自顶向下带备忘
优化:自底向上
1.6 状态转移方程怎么写
一 动态规划问题的特征
- 动态规划思想用来求解的是最优化问题。
- 原问题可以用包括子问题的递归式来描述。
- 最优子结构:原问题的最优解可以且必须由子问题的最优解得到。
- 重叠子问题:某些子问题在求解过程中反复出现,导致大量重复计算,所以要用①记忆化搜索(自顶向下的带备忘的方法)(普通递归的优化版本)②自底向上的方法
重叠子问题:某些子问题在求解过程中反复出现,导致大量重复计算,所以要用①记忆化搜索(自顶向下的带备忘的方法)(普通递归的优化版本)②自底向上的方法
例子:切割钢条的递归树(详见2)
1.2 最优子结构回顾下动态规划解决的是什么类型的问题?——最优化问题(optimization problem),那么最有子结构说的是:原问题的最优解由相关子问题的最优解组合而成。
并且这些子问题可以独立求解。并且原问题的最优解,一定要在子问题求出最优解之后,才由子问题的最优解“递归转移”(某些地方也叫“组合”,anyway这个动词用的比较模糊)而求出来。
1.3 贪心和动态规划的区别1.4 无后效性:如何恰当定义问题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),即如何写状态转移方程
二、 模板大框架(自顶向下,自底向上) 2.1 一般的递归方法李煜东著《算法竞赛进阶指南》,摘录如下::
为了保证计算子问题能够按照顺序、不重复地进行,动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之,动态规划对状态空间的遍历构成一张有向无环图,遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的「状态」,图中的边则对应状态之间的「转移」,转移的选取就是动态规划中的「决策」。
我的解释:
「有向无环图」「拓扑序」表示了每一个子问题只求解一次,以后求解问题的过程不会修改以前求解的子问题的结果;
换句话说:如果之前的阶段求解的子问题的结果包含了一些不确定的信息,导致了后面的阶段求解的子问题无法得到,或者很难得到,这叫「有后效性」,我们在当前这个问题第 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
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)设置储存状态的数组,状态转移方程依赖多少维变量来转移,就设多少维的数组,vector
dp(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://pwwzsj.com/article/coihgi.html