DP算法，经典，求解 如图所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
解答：从低到高依次计算，将其下相邻的数较大的加入自身，直到塔顶：
#include<stdio.h>
int ax[1002][1002];
int main()
{
int n,m,i,j;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
for(i=1;i<=m;i++)//输入数塔
for(j=1;j<=i;j++)
scanf("%d",&ax[i][j]);
for(i=i-1;i>0;i--)//从底层开始不断地取ax[i][j]和ax[i][j+1]之中比较大的那个加到上面的数ax[i][j]
for(j=1;j<i;j++)
{
if(ax[i][j]>=ax[i][j+1])
ax[i-1][j]+=ax[i][j];
else ax[i-1][j]+=ax[i][j+1];
}
printf("%d\n",ax[1][1]);
}
return 0;
}
第二题，天上掉馅饼：http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=3§ionid=2&problemid=8
要想求得最后最多能得到多少个，需要建立两个二维数组来记录某一秒某个位置的掉落数量和每一秒该位置的最大拾取量，从最后一秒进行计算，最后得到第0秒位置5的最多数量。
代码如下：
#include<iostream>
const int MAX=100001;
int DP[MAX][12];//保存第 i秒 j 位置 最多还能接到的馅饼
int Now[MAX][12];//保存第 i秒 j 位置落下的馅饼
using namespace std;
int main()
{
int n,pos,time,i,Time_MAX,maxn;
while(scanf("%d",&n)&&n)
{
memset(DP,0,sizeof(DP));
memset(Now,0,sizeof(Now));
Time_MAX=0;
for(i=0;i<n;i++)
{
scanf("%d%d",&pos,&time);
Now[time][pos]+=1;
if(Time_MAX<time)
{
Time_MAX=time;
}
}
for(i=0;i<=10;i++)
{
DP[Time_MAX][i]=Now[Time_MAX][i];
}
for(time=Time_MAX-1;time>=0;time--)
{
for(pos=0;pos<=10;pos++)
{
maxn=0;
if(pos>=1)
maxn=DP[time+1][pos-1];
if(DP[time+1][pos]>maxn)
maxn=DP[time+1][pos];
if(pos<=9&&DP[time+1][pos+1]>maxn)
maxn=DP[time+1][pos+1];
DP[time][pos]=Now[time][pos]+maxn;
}
}
printf("%d\n",DP[0][5]);
}
return 0;
}
