The Triangle
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 36138 | Accepted: 21615 |
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.
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
Source
试想一下：
这道题如果用枚举法（暴力思想） ，在数塔层数稍大的情况下（如 31） ，则需要列举出的路 径条数将是一个非常庞大的数目（2^30= 1024^3 > 10^9=10亿） 。
考虑一下：
从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取 到最大值，只要左右两道路径上的最大值求出来了才能作出决策。 同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层 一层推下去，直到倒数第二层时就非常明了。 如数字2，只要选择它下面较大值的结点 19 前进就可以了。所以实际求解时，可从底 层开始，层层递进，最后得到最大值。
结论：自顶向下的分析，自底向上的计算。
dp方程：
i == n(最后一行)
sum[n][j] = num[n][j];
i != n
sum[i][j] = max(sum[i+1][j],sum[i+1][j+1]) + num[i][j];
代码：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
int num[][],sum[][],n;
scanf("%d",&n);
memset(num,,sizeof(num));
memset(sum,,sizeof(sum));
for(int i = ; i <= n; i ++){
for(int j = ; j <= i; j ++){
scanf("%d",&num[i][j]);
}
}
for(int j = ; j <= n; j ++)
sum[n][j] = num[n][j];
for(int i = n-; i >= ; i --)
for(int j = ; j <= i; j ++){
sum[i][j] = max(sum[i+][j],sum[i+][j+]) + num[i][j];
}
printf("%d\n",sum[][]);
return ;
}