跨境派

跨境派

跨境派,专注跨境行业新闻资讯、跨境电商知识分享!

当前位置:首页 > 卖家故事 > C++ 动态规划 DP教程 (一)思考过程(*/ω\*)

C++ 动态规划 DP教程 (一)思考过程(*/ω\*)

时间:2024-03-26 07:06:23 来源:网络cs 作者:璐璐 栏目:卖家故事 阅读:

标签: 思考  过程  教程  规划  动态 
阅读本书更多章节>>>>

动态规划是一种思维方法,大家首先要做的就是接受这种思维方法,认同他,然后再去运用它解决新问题。

动态规划是用递推的思路去解决问题。

首先确定问题做一件什么事情?


对这件事情分步完成,分成很多步。

如果我们把整件事称为原问题,那么原问题去掉最后一步后,剩下的问题就称为子问题。
子问题和原问题是同性质的问题,子问题被原问题包含,原问题是在子问题的基础上推进一步得到的,所以用递推去求解。

子问题推进一步,得到原问题。哪些量在变化。这些变化的量用变量表示出来就是问题的状态。

子问题推进一步,这一步做了什么,就是决策。每一步的决策连续起来,就是做整件事的一个方案。

我们来看一道例题吧!ヾ(o・ω・)ノ


例1:组合问题,从n个不同物体中选择m个,求有多少种选择方案。

思考过程:
1、 题目要我们做一件什么事情?
答:选物体,确切的说是要我们从n个物体中选出m个物体。n和m尽管不知道是多少,但是肯定是一个确定的值,由输入数据确定,所以我们可以假设n=10,m=5,问题是要我们从10个物体中选出5个物体


2、 这件事分多少步去完成?
答:分10步完成,第一步考虑第一个物体选还是不选,第二步考虑第二个物体选还是不选,……,第10步考虑第10个物体选还是不选?


3、 原问题是什么?子问题是什么?
答:
整个问题是:从10个不同物体中选择5个。最后一步是确定第10个物体选还是不选。
如果第10个物体选了,那么去掉这一步,前9步还需要选择4个物体,所以剩下的子问题是从9个物体中选取4个。
如果第10个物体没有选,那么去掉这一步,在前9步还需要选择5个物体,所以剩下的子问题是从9个物体中选取5个。
原问题是10个中选5个,子问题是9个中选4个、9个中选5个


4、 子问题和原问题是同一个性质的问题,用数学符号描述这个问题,需要几个变量才能体系原问题和子问题的差异,各自表示什么含义?
答:原问题和子问题中,备选物体的规模在变化,选出来的物体数目在变化,所以用两个变量来表示问题变化的量:a表示备选物体的数目,b表示选出的物体数目,f(a,b)整个符号的含义就是从a个不同物体中选取b个物体的方案数,这里的f就是表示求解目标,方案数。
很显然,当a取值10,b取值5时,f(10,5)表示原问题,f(9,5)、f(9,4)表示子问题。用问题和子问题都是用同一个模式来表示,这就是状态。


5、 有了状态,我们就可以寻找子问题和原问题之间的递推关系了。
答:
原问题去掉最后一步,得到的子问题,寻找二者之间的关系。
f(a,b)表示从a个不同物体中选取b个,得到的方案数。
对最后一步分两种情况讨论:
选取第a个物体,则方案数等价于从剩下的a-1个物体中选取b-1个,即f(a-1,b-1)
不选第a个物体,则方案数等价于从剩下的a-1个物体中选取b个,即f(a-1,b)

所以得到一个递推方程:f[a,b]=f[a-1,b-1]+f[a-1,b]


6、 状态在计算机中用数组表示,数组第一维下标表示第一个变量,第二维下标表示第二个变量。则一个状态对应一个数组元素,状态之间递推等价于给数组元素递推赋值。

好了看前面的文章,你应该知道了如何思考动态规划的题目!

但是一道题是不够的,要做很多道题,你才能彻底的理解动态规

划的解题思路,从而得到方程,写出代码!ヽ(・ω・´メ)

话不多说,我们再来看一道题目吧!

【洛谷】P1255 数数梯

原题地址:https://www.luogu.org/problem/P1255

思路:
这个题目隐藏深一些。
题目要我们求等式的个数,我们可以穷举等号右边的和数,如果我们把数列从小到大排列,这样等号左边的数就全部位于穷举的数的左边(想不明白为什么需要排序,暂时可以放一放,假设数列就是已经排好序的)。
对于每个穷举的合数,我们目标是寻找在他左边有多少个合法的式子的和等于他。
思考过程:
1、 题目要我们做一件什么事情?
答:求所有的数学式子,确切的说,当我们穷举第i个和数时,是要我们从i-1个数中选出若干个数,使得这些数的和是a[i]。i是穷举的,是定值。
2、这件事分多少步去完成?
答:分i-1步完成,第一步考虑第一个数选还是不选,第二步考虑第二个数选还是不选,……,第i-1步考虑第i-1个数选还是不选?
3、原问题是什么?子问题是什么?
答:
整个问题是:从i-1个数中选择若干个,使得总和是a[i]。最后一步是确定第i-1个数选还是不选。
如果第i-1个数选了,那么去掉这一步,前i-2步还需要选择若干个数,使得和为a[i]-a[i-1],所以剩下的子问题是从i-2个数中选若干个,使得总和是a[i]-a[i-1]。
如果第i-1个物体没有选,那么去掉这一步,在前i-2步还需要选择若干个数使得总和为a[i],所以剩下的子问题是从i-2个数中选若干个,使得总和是a[i]。
原问题是从i-1个数中选择若干个,使得总和是a[i]。子问题是从i-2个数中选若干个,使得总和是a[i]-a[i-1];i-2个数中选若干个,使得总和是a[i]。
4、子问题和原问题是同一个性质的问题,用数学符号描述这个问题,需要几个变量才能体系原问题和子问题的差异,各自表示什么含义?
答:原问题和子问题中,备选数的规模在变化,选出来的和在变化,所以用两个变量来表示问题变化的量:x表示备选物体的数目,y表示选出的物体数目,f(x,y)整个符号的含义就是从x个数中选若干个使得总和为y的方案数,这里的f就是表示求解目标,方案数。
很显然,当x取值i-1,y取值a[i]时,f(i-1,a[i])表示原问题,f(i-2,a[i]-a[i-1])、f(i-2,a[i])表示子问题。用问题和子问题都是用同一个模式来表示,这就是状态。
5、有了状态,我们就可以寻找子问题和原问题之间的递推关系了。
答:
原问题去掉最后一步,得到的子问题,寻找二者之间的关系。
f(x,y)表示从x个数中选若干个使得和为y,得到的方案数。
对最后一步分两种情况讨论:
选取第x个数,则方案数等价于从剩下的x-1个数中选若干个使得和为y-a[x],即f(x-1,y-a[x])
不选第x个数,则方案数等价于从剩下的x-1个数中选若干个使得和为y,即f(x-1,y)

所以得到一个递推方程:f[x,y]=f[x-1,y-a[x]]+f[x-1,y]
使用该递推方程,可以求每一个阶段的状态
6、状态在计算机中用数组表示,数组第一维下标表示第一个变量,第二维下标表示第二个变量。则一个状态对应一个数组元素,状态之间递推等价于给数组元素递推赋值。
 

好了,本篇文章就结束了,如果喜欢就记得三连哦φ(>ω<*) ,记得多多做题哦,bye!ヾ(o・ω・)ノ

阅读本书更多章节>>>>

本文链接:https://www.kjpai.cn/gushi/2024-03-26/148702.html,文章来源:网络cs,作者:璐璐,版权归作者所有,如需转载请注明来源和作者,否则将追究法律责任!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。

文章评论