明显是一个动态规划，有两种思路，一种是至上而下的，一种是至下而上的，让我联想到了几个大国家的革命和改革，我支持改革，革命总是要留下一些历史痕迹，漏洞，所以我选择的是至下而上的改革。至下而上的DP有什么好处呢？好处多了，因为没有任何特殊情况要考虑，如果是至上而下的DP的话，首先有特殊情况，对于每一个内层循环的值等于外层的值的话，但是这个处理得好的话还是可以做到不要多余的if来判断i是否等于j，在输出答案时不需要遍历底层，在这里的代码我犯了一个小错误导致我的代码丢了最后一个点。
犯的错误：数组的下标使用错误了，在极限值（1000）时会溢出！
提交了两次，代码如下：
LANG: C
ID: yylogoo2
PROG: numtri
/
#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int f[1000][1000];
int n;
int main(void)
{
int i, j;
freopen("numtri.in", "r", stdin);
freopen("numtri.out", "w", stdout);
scanf("%d", &n);
for(i = 0; i < n; i++){
for(j = 0; j <= i; j++){
scanf("%d", &f[i][j]);
}
}
/
Mistack 1:
下面的i我写的是i–, 因为前面的代码. 但是删掉之后忘记修改这里了,
i要从n – 2开始枚举..
/
for(i = n – 2; i >= 0; i–){
for(j = 0; j <= i; j++){
f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
}
}
printf("%d\n", f[0][0]);
return 0;
}