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

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

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

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

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

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

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

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

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

我们来看一道例题吧!ヾ(ｏ･ω･)ﾉ

例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！ヾ(ｏ･ω･)ﾉ

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

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