佛山市专业的网站设计,wordpress 左导航,壹搜网站建设,做视频网站空间要多大动态规划是一种思维方法#xff0c;大家首先要做的就是接受这种思维方法#xff0c;认同他#xff0c;然后再去运用它解决新问题。
动态规划是用递推的思路去解决问题。 首先确定问题做一件什么事情#xff1f; 对这件事情分步完成#xff0c;分成很多步。 如果我们把整件…动态规划是一种思维方法大家首先要做的就是接受这种思维方法认同他然后再去运用它解决新问题。
动态规划是用递推的思路去解决问题。 首先确定问题做一件什么事情 对这件事情分步完成分成很多步。 如果我们把整件事称为原问题那么原问题去掉最后一步后剩下的问题就称为子问题。 子问题和原问题是同性质的问题子问题被原问题包含原问题是在子问题的基础上推进一步得到的所以用递推去求解。 子问题推进一步得到原问题。哪些量在变化。这些变化的量用变量表示出来就是问题的状态。 子问题推进一步这一步做了什么就是决策。每一步的决策连续起来就是做整件事的一个方案。
我们来看一道例题吧!ヾ(ω)
例1组合问题从n个不同物体中选择m个求有多少种选择方案。 思考过程 1、 题目要我们做一件什么事情 答选物体确切的说是要我们从n个物体中选出m个物体。n和m尽管不知道是多少但是肯定是一个确定的值由输入数据确定所以我们可以假设n10m5问题是要我们从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取值10b取值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-1y取值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ヾ(ω)
