参考

　　先从一个基本的例子上手

　　我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？

　　令n=f(v),表示n个硬币可凑齐v元,现在需要求n的最小值

　　当v为0时，f(0)=0

　　当v为1时，可以取1元硬币了，我取1个1元硬币，f(1)=1+f(1-1)　

　　当v为2时，可以取1元硬币，我取1个1元硬币，f(2)=1+f(2-1)=2

　　当v为3时，可以取1元硬币和3元硬币，我可以取1个1元或者1个3元，f(3)=min(1+f(3-1),1+f(3-3))=1

　　当v为4时，可以取1元硬币和3元硬币，我可以取一个1元或者1个3元，f(4)=min(1+f(4-1),1+f(4-3))=2

　　当v为5时，可以取1元硬币、3元硬币和5元硬币，f(5)=min(1+f(5-5),1+f(5-3),1+f(5-1)))=1

　　够了，通项f(v)=min(f(v-x[j])+1)  x[j]表示各种面值

1 int getMin(int v,vector
     
      & x){             //x[0]=1,x[1]=3,x[2]=5 2     int temp[100]={
   0};                        //其实只用保证temp[0]=0就可以了 3     int flag;                                  4     for(int i=1;i<=v;++i){ 5         flag=1000;                              6         for(int j=0;j
      
       temp[i-x[j]]+1){     8                 flag=temp[i-x[j]]+1; 9             }10         }11         temp[i]=flag;12     }13     return temp[v];14 }
      
     

　　小结一下，动态规划就是在寻找状态方程f(v)=min(f(v-x[j])+1)

　　再上一个例子

　　找出序列的最长非递减子序列的长度，eg，序列为5,3,4,8,6,7

　　令n=f(v)，表示前v个数的最长非递减子序列为n

　　当v=1时，f(1)=1

　　当v=2时，第2个数比第1个小，f(2)=1

　　当v=3时，第3个数比第2个大，f(3)=f(2)+1

　　当v=4时，第4个数比第1、2、3个数大，f(4)=max(f(1)+1,f(2)+1,f(3)+1)

　　够了，状态方程f(v)=max(1,f(j)+1)    j<v&&a[v]>=a[j]

 

1 int getMax(vector
     
      & a){ 2     if(a.empty())return 0; 3     int b[1000]={
   1}; 4     int flag=1; 5     for(int i=0;i
      
       =0;--j){ 7             if(a[i]>=a[j]&&b[i]