PKU ACM 1163

Description

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

(Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right. 

动态规划问题，建立一个数组，从下到上，保存各节点的最大值

#include <stdio.h>

#define MAX 100

int input[MAX][MAX];

int main()

{

int n,i,j;

scanf("%d",&n);

for(i=0;i<n;i++)

for(j=0;j<i+1;j++)

scanf("%d",input[i]+j);

for(i=n-2;i>=0;i--)

for(j=0;j<i+1;j++)

input[i][j]+=input[i+1][j]>input[i+1][j+1]?input[i+1][j]:input[i+1][j+1];

printf("%d",input[0][0]);

return 0;

}