参考阮行止先生在知乎上的文章
https://www.zhihu.com/question/23995189/answer/613096905
【作者：阮行止 来源：知乎】
看了这篇文章后感觉dp我等凡人也是看得懂的，又重新捡起来准备学习。写这篇随笔也是为了给日后自己遗忘时写个楔子。
借用上面文章中的例子来复习一下动态规划。
第一个钞票问题。
如何用最少的钱币组成金额w（钱币的面额不为【10,5,2,1】时）？
(ps: 为什么国家发行的钱币面额是【100,50,20,10,5,2,1】？ 就结果来说致使较小面额的两种面值加起来不超过上一个面额，减少了组合时需要考虑的情况。
ps: 不过为什么不用二进制来做面额，前两天刚看完二进制枚举qwq）
设钱币面额为【11,5,1】，要凑够w= 15，则此时不能使用贪心法。
贪心：15= 11+ 1+ 1+ 1+ 1。共需用5 张钱币。
而实际上，15= 5* 3。只需三张便可以凑够w。此时我们发现了贪心的不足，贪心会尽量让剩下的w 变得更小，但一旦钞票的面额发生了变化，这种策略就不成立了。
贪心是一种只考虑眼前的行为。但局部最优解不一定是全局最优解，这时便是我们需要动态规划的原因所在。
暴力枚举固然可行，但十分浪费时间。暴力枚举时，我们枚举出了凑足w 所需要使用的硬币，但这根本人无关紧要；我们只需要最后的结果，至于此结果是怎么来的，我们并不关心。那么我们反过来考虑，我们要凑足金额w 需要的钱币数量，实际上只与凑足前一步的钱币数量有关，是与构成金额w- 11，w- 5，w- 1的钱币数量有关。
实际上 : F(w)= min (F(w- 11), F(w- 5), F(w- 1) )+ 1； （式子①）
此时，问题F(w)的结果就与F(w- 11), F(w- 5), F(w- 1) 的结果有关了，我们把求F(w)的问题转化成了求若干个F(c)的子问题，这就是动态规划。
将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。
上面的式子①便是上面问题的状态转移方程。
#include<cstdio> #include<iostream> #include<cmath> using namespace std; int main () { int f[105]; f[0] = 0; int w, cost; //f[w]= cost= min (f[w- c1], f[w- c2], ..., f[w- ci])+ 1; const int inf = 0x3f3f3f3f; //inf 取 int 最大值; while(cin >> w) { for (int c = 1; c <= w; c ++) { cost= inf; // 注意“+1”放在括号内，否则会出错,如下 // if (c- 1>= 0) cost= min (cost, f[c- 1])+ 1; // if (c- 5>= 0) cost= min (cost, f[c- 5])+ 1; // if (c- 11>= 0) cost= min (cost, f[c- 11])+ 1; // 结果则会多加1，第一次粗心就错了，太菜了 if (c- 1>= 0) cost= min (cost, f[c- 1]+ 1); if (c- 5>= 0) cost= min (cost, f[c- 5]+ 1); if (c- 11>= 0) cost= min (cost, f[c- 11]+ 1); f[c]= cost; } // for (int i = 0; i <= w; i ++) // { // cout << f[i] << endl; // } cout << f[w] << endl; } return 0; }
动态规划中的两个概念。无后效性和最优子结构性质。
无后效性就是说“如果在某个阶段上过程的状态已知，则从此阶段以后过程的发展变化仅与此阶段的状态有关，而与过程在此阶段以前的阶段所经历过的状态无关。”，一言蔽之，便是“未来与过去无关”。某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段k中的状态只能通过阶段k+1中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。
最优子结构性质。大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”。例如最短路径问题就有最优子结构属性：如果一个节点x在开始节点u，终点为v的最短路径上的时候，那么从u到v的最短路径就是从u到x的最短路径加上从x到v的最短路径。像Floyd–Warshall和Bellman–Ford的标准，最短路径算法就是典型的动态规划的例子。
动态规划问题的共同特性是，都能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。
一道动态规划问题其实就是一个递推问题。假设当前决策结果是f[n]，则最优子结构就是要让f[n-k]最优，最优子结构性质就是能让转移到n的状态是最优的；并且具有无后效性，保证前面的历史与后面的决策没有关系，让后面的决策能安心地利用前面的局部最优解。
套用文章中的话（以下为链接文章中的内容）：
【DP的操作过程】
①将一个大问题转化成几个小问题；
②求解小问题；
③推出大问题的解。
【如何设计DP算法】
下面介绍比较通用的设计DP算法的步骤。
首先，把我们面对的局面表示为x。这一步称为设计状态。
对于状态x，记我们要求出的答案(例题中为最少使用钱币)为f(x).我们的目标是求出f(T).
找出f(x)与哪些局面有关（记为p），写出一个式子（称为状态转移方程），通过f(p)来推出f(x).
【DP三连】
设计DP算法，往往可以遵循DP三连：
我是谁？ ——设计状态，表示局面
我从哪里来？
我要到哪里去？ ——设计转移
设计状态是DP的基础。接下来的设计转移，有两种方式：一种是考虑我从哪里来（本文之前提到的两个例子，都是在考虑“我从哪里来”）；另一种是考虑我到哪里去，这常见于求出f(x)之后，更新能从x走到的一些解。这种DP也是不少的，我们以后会遇到。
总而言之，“我从哪里来”和“我要到哪里去”只需要考虑清楚其中一个，就能设计出状态转移方程，从而写代码求解问题。前者又称pull型的转移，后者又称push型的转移。
#include<cstdio> #include<iostream> #include<cmath> using namespace std; int main () { int f[105]; f[0] = 0; int w; const int inf = 0x3f3f3f3f; while(cin >> w) { fill (f+ 1, f+ w, inf); for (int c = 0; c <= w; c ++) //要记得从0 开始 { if (w >= c+ 1) f[c+ 1]= min (f[c+ 1], f[c]+ 1); if (w >= c+ 5) f[c+ 5]= min (f[c+ 5], f[c]+ 1); if (w >= c+ 11) f[c+ 11]= min (f[c+ 11], f[c]+ 1); } // for (int i = 0; i <= w; i ++) // { // cout << f[i] << endl; // } cout << f[w] << endl; } return 0; }
洛谷上这道题的变形 P2214 [USACO14MAR]哞哞哞Mooo Moo
农民约翰忘记了他到底有多少头牛，他希望通过收集牛叫声的音量来计算牛的数量。
他的N (1 <= N <= 100)个农场分布在一条直线上，每个农场可能包含B (1 <= B <= 20)个品种的牛，一头品种i的牛的音量是V(i) ，(1 <= V(i) <= 100)。一阵大风将牛的叫声从左往右传递，如果某个农场的总音量是X，那么将传递X-1的音量到右边的下一个农场。另外，一个农场的总音量等于该农场的牛产生的音量加上从上一个农场传递过来的音量（即X-1）。任意一个农场的总音量不超过100000。
请计算出最少可能的牛的数量。
输入格式
* Line 1: The integers N and B.
* Lines 2..1+B: Line i+1 contains the integer V(i).
* Lines 2+B..1+B+N: Line 1+B+i contains the total volume of all mooing in field i.
输出格式
* Line 1: The minimum number of cows owned by FJ, or -1 if there is no configuration of cows consistent with the input.
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int maxn = 100005; const int inf = 0x3f3f3f; int B_Kind_Cost[25]; int N_Sum[105]; int Min_Cost[maxn]; int main() { int N, B; while (cin >> N >> B) { for (int i = 0; i < B; i ++) { cin >> B_Kind_Cost[i]; } for (int i = 0; i < N; i ++) { cin >> N_Sum[i]; } fill(Min_Cost, Min_Cost+ 100000, inf); Min_Cost[0]= 0; for (int i = 1; i < 100000; i ++) { int cost= inf; for (int j = 0; j < B; j ++) { if (i- B_Kind_Cost[j]>= 0) cost= min(cost, Min_Cost[i- B_Kind_Cost[j]]+ 1); } Min_Cost[i]= cost; } int tmp= 0, sum= 0; // for (int i = 0; i < 500; i ++) // { // cout << i << " " << Min_Cost[i] << endl; // } for (int i = 0; i < N; i ++) { if (! i) tmp= 0, sum= 0; sum += Min_Cost[N_Sum[i]- tmp]; tmp = max(0, N_Sum[i]- 1); //防止因为这一个牛场时的声音为0,而导致下个牛场多+1的声音; } cout << sum << endl; } return 0; }