动态规划即是一个重点，又是一个难点。
今天终于做出了一题像样的动态规划题。
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


分析：
题意简化为：
从第一行开始走到最后一行，每步可以向下走或右下走。
所求即为从第一行走到最后一行经过的数总和的最大值。
令p[][]存储input。
5
7
3 8
8 1 0
2 7 4 4
|     \ |  \
4 5 2 6 5

如上图，令i为行，j为列,
d[i][j]为从第一行走到第i行第j列的最大值。
对于(i,j)这个点，它可以从不同方向走来，如图' | '代表从上方走来，' \ '代表从左上方走来。

则动态规则方程为：
                  {     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)

结果为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;
}