动态规划是一种思维方法,大家首先要做的就是接受这种思维方法,认同他,然后再去运用它解决新问题。 动态规划是用递推的思路去解决问题。 首先确定问题做一件什么事情? 对这件事情分步完成,分成很多步。 如果我们把整件事称为原问题,那么原问题去掉最后一步后,剩下的问题就称为子问题。 子问题和原问题是同性质的问题,子问题被原问题包含,原问题是在子问题的基础上推进一步得到的,所以用递推去求解。 子问题推进一步,得到原问题。哪些量在变化。这些变化的量用变量表示出来就是问题的状态。 子问题推进一步,这一步做了什么,就是决策。每一步的决策连续起来,就是做整件事的一个方案。 我们来看一道例题吧!ヾ(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・ω・)ノ