首先，动态规划方法适合的题型4个基本特点是： 1、最优子结构，当前一个状态得到最佳解时，当前状态在前一个状态下一定有最佳解； 2、子问题重叠，每个状态下要解决的问题除参数不同外，其本质是一样的； 3、有边界，当解决了最后一个子问题时，整个问题得解； 4、子问题独立，解决一个子问题时不依赖于另一个同级的子问题，只与它的母问题有关； 当存在这四个特点时很大程度上可以确定用动态规划的方法解觉了。 而解决动态规划问题的关键在于写出状态转移方程式，一般来说，对应一个状态下，对某件事情是否执行，这是两个子问题，每个子问题都可以递归下一个状态，最终到达边界条件返回，再判断最开始的状态下两个子问题的最优解，即是整个问题的答案。
我再使用国王的金矿的例子来解释动态规划的实现过程： 有一个国家的国王为了增强国力要开采已探明储量的5座金矿，开采每一座金矿所需的人员是固定的，而且为了能顺利将金矿开采又不耽误人民生活，国王决定只调配500人去挖金矿，要同时开采所有金矿，而且每个人民只开采一次，他要向国会说明开采金矿能带来多少金子，但是问题来了，由于没有足够的人手一次性把所有金矿都开采，怎么搞清能获得最多金子的数量是个难题。
苦思良久，国王有一个好办法了，他想，我只要知道前4座金矿最多能开采多少金子就能计算出开采所有金矿最多能获得多少金子了。他对左丞相说我不开采第5座金矿，你想办法告诉我开采前4座金矿最多能获得多少金子，又对右丞相说我要开采第5座金矿，用掉100个劳力，你想办法告诉我开采前4座金矿最多能获得多少金子。
这下子，国王不急丞相急了，左丞相们想啊， 国王这么聪明，要我告诉他前4座金矿最多能开采多少金子，那我是不是也可以学学国王让大臣告诉我前三座金矿最多能挖多少金子呢，于是左丞相叫来两个大臣，对其中一个说，我要240人用于开采第4、5座金矿，其它人手给你调配的话，你告诉我前三座金矿最多能开采多少金子，又对另一个说我要用100人开采第5座金矿，第4座不开采，其它人手给你调配的话你告诉我前三座金矿最多能挖多少金子。
右丞相焦头烂额之际，打听到左丞相有此妙计，不禁豁然开朗，只要学着国王的做法，把前几座金矿的最大开采量交给属下去解决，我只要决定一座金矿是否开采得出较大值不就得到答案了吗？于是，右丞相也依法炮制，也叫两个大臣，让他们分别在开采与不开采第4座金矿的前提下调查前三座金矿的最大产量。
接下来，这个计算金矿最大开采量的办法被传开了，这个国家的人民，纷纷赞扬国王的聪明，他们把这种办法叫做国王的金矿。
国王的故事果然很生动形象啊，知道i-1座金矿的最大产量就一定能知道i座金矿的最大产量，这是最优子结构，每个人要知道i座金矿的最大产量就必须知道知道i-1座金矿的最大产量，这是子问题重叠，最终当考虑第1座金矿的最大产量时，只要看是否有足够人手开采第1座金矿，有的话，答案是已探明的储量，没有的话就是0，然后答案汇报到上级，上级再得出第2座金矿开采与不开采得出的较大产量，再往上汇报…,这就是边界，而每个人从上级得到的前提都是不同的，上级决定开不开采，再将这个前提之一告诉下属，而下属不需要考虑上级给另一个下属什么前提，这是子问题独立。
解法：
我们来分析一下最优子结构和最终问题的关系。换句话说，4个金矿的最优选择和5个金矿的最优选择之间，是什么样的关系？
5个金矿的最优选择，就是（前4座金矿10工人的挖金数量）和（前4座金矿7工人的挖金数量+第5座金矿的挖金数量）的最大值。
下面，我们把金矿数量设为N，工人数设为W，金矿的黄金量设为数组G[]，金矿的用工量设为数组P[]。
那么5座金矿和4座金矿的最优选择之间存在这样的关系：F(5,10) = MAX( F(4,10), F(4,10-P[4])+G[4] ) 注意：数组下标从0开始。
最后我们还需要确定一下，这个问题的边界是什么？
边界两种情况：（1）只有1座金矿，也就是N=1的时候。这时候没得选，只能挖这座唯一的金矿，得到的黄金数量就是G[0]。（2）如果给定的工人数量不够挖取第1座金矿，也就是 W < P[0] 的时候，那么得到的黄金数就是0了。
用公式来表达如下：
经过上面的分析，我们可以得出这个问题完整的状态转移方程：
F (N,W) = 0 （当N <= 1, W < P[0]）;
F (N,W) = G[0] （当N == 1, W >= P[0]）;
F (N,W) = F(N-1, W) （当N > 1, W < P[N - 1]）;
F (N,W) = MAX ( F(N-1, W) , F(N-1，W - P[ N-1]) + G[N-1])（当N > 1, W >= P[N - 1]）;
先贴出递归求解代码
//动态规划递归解法 // 题目：获得金矿最优收益 /* w 表示工人数量 n 表示可选金矿数量 p 表示金矿开采需要的工人数量 g 表示金矿储量 */ #include<iostream> #include<cmath> #include<cstring> using namespace std; int GetBest( int w,int n,int p[],int g[]){ //工人数量为零或者没有东西可以采 if(w==0||n==0){ return 0; } //当工人不够挖掘第N个金矿时 if(w<p[n-1]){ return GetBest(w,n-1,p,g); } //在两种最有子结构中找到最有解，也就是最大值 return max(GetBest(w,n-1,p,g),GetBest(w-p[n-1],n-1,p,g)+g[n-1]); } int main(int argc, char const *argv[]) { int w=10; int p[]={5,5,3,4,3}; int g[]={400,500,200,300,350}; int length=sizeof(g)/sizeof(int); cout<<GetBest(w,length,p,g)<<endl; return 0; }非递归代码贴出，为什莫用非递归呢？为了提高算法运行效率。
int GetBest(int w,int length,int p[],int g[]){ int resulttable[length+1][w+1]={0}; // for(int i=0;i<length+1;i++){ // for(int j=0;j<w+1;j++){ // cout<<resulttable[i][j]<<" "; // } // cout<<endl; // } memset(resulttable, 0, sizeof resulttable); for(int i=1;i<length+1;i++){ for(int j=1;j<w+1;j++){ if(j<p[i-1]){ resulttable[i][j]=resulttable[i-1][j]; } else{ resulttable[i][j]=max(resulttable[i-1][j],(resulttable[i-1][j-p[i-1]]+g[i-1])); } } } cout<< resulttable[length][w]<<endl; return 0; }
上面的代码的空间复杂度为o（nw），我们可以利用一维数组降低空间复杂度
这里有一个很重要的点就是内循环必须从后往前进行，因为从前往后进行覆盖的时候，后面的数据计算会根据前面覆盖后的数据进行计算，所以必须从后到前
void GetBest1(int w,int length,int p[],int g[]){ int result[w+1]; memset(result,0,sizeof result); for(int i=1;i<=length;i++){ for(int j=w;j>=1;j--){ if(j>=p[i-1]){ result[j]=max(result[j],result[j-p[i-1]]+g[i-1]); } } } cout<<result[w]<<endl; }完整代码展示
#include<iostream> #include<cmath> #include<cstring> using namespace std; int GetBest(int w,int length,int p[],int g[]){ int resulttable[length+1][w+1]={0}; // for(int i=0;i<length+1;i++){ // for(int j=0;j<w+1;j++){ // cout<<resulttable[i][j]<<" "; // } // cout<<endl; // } memset(resulttable, 0, sizeof resulttable); for(int i=1;i<length+1;i++){ for(int j=1;j<w+1;j++){ if(j<p[i-1]){ resulttable[i][j]=resulttable[i-1][j]; } else{ resulttable[i][j]=max(resulttable[i-1][j],(resulttable[i-1][j-p[i-1]]+g[i-1])); } } } cout<< resulttable[length][w]<<endl; return 0; } void GetBest1(int w,int length,int p[],int g[]){ int result[w+1]; memset(result,0,sizeof result); for(int i=1;i<=length;i++){ for(int j=w;j>=1;j--){ if(j>=p[i-1]){ result[j]=max(result[j],result[j-p[i-1]]+g[i-1]); } } } cout<<result[w]<<endl; } int main(int argc, char const *argv[]) { int w=10; int p[]={5,5,3,4,3}; int g[]={400,500,200,300,350}; int length=sizeof(g)/sizeof(int); GetBest(w,length,p,g); GetBest1(w,length,p,g); return 0; }
