動(dòng)態(tài)規(guī)劃即是一個(gè)重點(diǎn)，又是一個(gè)難點(diǎn)。
今天終于做出了一題像樣的動(dòng)態(tài)規(guī)劃題。
Problem Id:1163??User Id:beyonlin_SCUT
Memory:100K??Time:0MS
Language:C++??Result:Accepted
http://acm.pku.edu.cn/JudgeOnline/problem?id=1163

The Triangle
Time Limit:1000MS? Memory Limit:10000K
Total Submit:3415 Accepted:1988

Description

7

3   8

8   1   0

2   7   4   4

4   5   2   6   5


(Figure 1)

Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.

Output
Your program is to write to standard output. The highest sum is written as an integer.

Sample Input

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

Sample Output
30


分析：
題意簡(jiǎn)化為：
從第一行開始走到最后一行，每步可以向下走或右下走。
所求即為從第一行走到最后一行經(jīng)過的數(shù)總和的最大值。
令p[][]存儲(chǔ)input。
5
7
3 8
8 1 0
2 7 4 4
|?????\ |? \
4 5 2 6 5

如上圖，令i為行，j為列,
d[i][j]為從第一行走到第i行第j列的最大值。
對(duì)于(i,j)這個(gè)點(diǎn)，它可以從不同方向走來，如圖' | '代表從上方走來，' \ '代表從左上方走來。

則動(dòng)態(tài)規(guī)則方程為：
???????????????? ?{?????d[i-1][1]+p[i][1]???(j=1)
d[i][j]=Max{???? Max( d[i-1][j-1] , d[i-1][j] ) + p[i][j]???(1<j<i)
????????????????? {???? d[i-1][i-1]+p[i][i]???(j=i)

結(jié)果為Max(d[n][j]) , (1<=j<=n)

代碼如下：

#include<cstdio>
int p[100][100];
int d[100][100];
int Max(int a,int b)
{return a>b?a:b;}
int main()
{
	int i,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		int j;
		for(j=1;j<=i;j++)
			scanf("%d",p[i]+j);
	}
	d[1][1]=p[1][1];
	for(i=2;i<=n;i++)
	{
		int j;
		d[i][1]=d[i-1][1]+p[i][1];
		for(j=2;j<=i;j++)
			d[i][j]=Max(d[i-1][j-1],d[i-1][j])+p[i][j];
		d[i][i]=d[i-1][i-1]+p[i][i];
	}
	int max=0;
	for(i=1;i<=n;i++)
	{
		if(d[n][i]>max)
			max=d[n][i];
	}
	printf("%d\n",max);
	return 0;
}