动态规划是一种思维方法，大家首先要做的就是接受这种思维方法，认同他，然后再去运用它解决新问题。
动态规划是用递推的思路去解决问题。
首先确定问题做一件什么事情？
对这件事情分步完成，分成很多步。 如果我们把整件事称为原问题，那么原问题去掉最后一步后，剩下的问题就称为子问题。 子问题和原问题是同性质的问题，子问题被原问题包含，原问题是在子问题的基础上推进一步得到的，所以用递推去求解。 子问题推进一步，得到原问题。哪些量在变化。这些变化的量用变量表示出来就是问题的状态。 子问题推进一步，这一步做了什么，就是决策。每一步的决策连续起来，就是做整件事的一个方案。
我们来看一道例题吧!ヾ(ｏ･ω･)ﾉ
例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.toymoban.com/news/detail-713846.html
文章来源：https://www.toymoban.com/news/detail-713846.html
到了这里，关于C++ 动态规划 DP教程 （一）思考过程(*/ω＼*)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
