动态规划（programming在这里是规划的意思）算法设计技术由二十世纪五十年代的美国卓越数学家理查德.贝尔曼发明，它主要用来解决这种问题：
问题是由交叠的子问题构成的，按照动态规划，与其对子问题一次又一次地求解，还不如对每个较小的子问题只求解一次(斐波那契数列)并把结果记录在表中，这样就可以从表中得到原始问题的解。
三大经典例题
1.币值最大化问题
给定一排n个硬币，其面值均为整数C1, C2, ..., Cn, 这些整数并不一定两两不同。问如何选择硬币，使得在其原始位置互不相邻的条件（也就是说选了第i个就不能选第i+1个）下，所选硬币的总金额最大。
设最大可选金额为F(n),首先根据是否包含Cn将所有的可选计划分为两组
- 包含Cn，F(n)=Cn+F(n-2) 互不相邻,选了Cn就不能选Cn-1
- 不包含Cn，F(n)=F(n-1)
在这里F(n-1~0)是已经得出的，所以使F(n)取最大值的就是F(n-1)和Cn+F(n-2)中的最大值
初始条件F(0)=0（啥都没选当然为0）
假设 n=2 C1=5,C2=4。
- F(0)=0
- F(1)=5
- F(2)=5
容易看出这里的F(n)选的是2
综上所述
F(n)=max(F(n-1),Cn+F(n-2));
//自底向上求最大金额即从F(2)开始求知道F(n)
#include <iostream>
#include <algorithm>
using namespace std;
int CoinRow(int c[],int n)//下标从1开始
{
int F[n];
F[0]=0;
F[1]=c[1];
for(int i=2;i<n;i++)
F[i]=max(c[i]+F[i-2],F[i-1]);
return F[n-1];
}
int main()
{
int n=7;
int c[n]={0,5,1,2,10,6,2};
cout<<CoinRow(c,n);
return 0;
}
- 找零问题
需找零金额为n，最少要用多少面值为d1<d2<...<dn的硬币
设F(n)为找零n元所需要的最少硬币数
显然F(0)=0;
F(n)=F(n-di)+1;
思考一下上述公式是成立的，因此选取使n-di最小(但是不能为负数)的di才能获得最小的F(n),使用与上题相同的思想从底向上计算。
#include <iostream>
using namespace std;
int ChangeMaking(int D[],int length,int n)//0舍去不用
{
int F[n+1];
F[0]=0;
for(int i=1;i<=n;i++)
{
int temp=D[length-1]+1;
for(int j=1;j<length&&i>=D[j];j++)
temp=min(F[i-D[j]],temp);
F[i]=temp+1;
}
return F[n];
}
int main()
{
int D[3]={1,3,4};
cout<<ChangeMaking(D,3,6);
return 0;
}
- 硬币收集问题
在n*m格木板中放有一些硬币，每格的硬币数目最多一个，在木板左上方的机器人要尽可能多的收集硬币，机器人只能向右、向下运动，找出机器人能找到的最大硬币数并给出相应的路径。
设F[i,j]为机器人移动到[i,j]收集到的硬币数,M[row,col]为硬币分布
因为只能向右或向下移动因此
F[i,j]=max(F[i,j-1],F[i-1,j])
对于第一行和第一列
F[1,i]=F[1,i-1]+M[1,i] 2<=i<=col
F[j,1]=F[j-1,1]+M[j,1] 2<=j<=row
这样跌倒计算出所有F[i,j]的值，F[row,col]即为硬币最大值，要获得路径就对max进行改造，记下两者中最大者的坐标(注意不止一条可行路径，如果两者相等就可以划分成两条路径)
#include<iostream>
using namespace std;
int RobotCollection(int M[][7],int row,int col)
{
int F[row][col];
F[1][1]=M[1][1];
for(int j=2;j<col;j++)
F[1][j]=F[1][j-1]+M[1][j];
for(int i=2;i<row;i++)
{
F[i][1]=F[i-1][1]+M[i][1];
for(int j=2;j<col;j++)
F[i][j]=max(F[i][j-1],F[i-1][j])+M[i][j];
}
return F[row-1][col-1];
}
int main()
{
int M[6][7]={
{0,0,0,0,0,0,0},
{0,0,0,0,0,1,0},
{0,0,1,0,1,0,0},
{0,0,0,0,1,0,1},
{0,0,0,1,0,0,1},
{0,1,0,0,0,1,0}
};
cout<<RobotCollection(M,6,7);
return 0;
}
