有名的数塔问题，对于刚接触DP的同学，应该就是这题吧，这里说一下我的想法和官方的代码。
这题肯定是不可以用最原始的递归的，对于初学DP的同学，可能会用到DP的递归调用，那只是第一步，接着你会把递归的化成非递归的，然后你可能还会想到从下往上计算而不是从上往下计算，因为当你用从上往下计算时，要考虑数组是否越界(也就是没行的第一个，这个数的左上没有数，还有就是每一行的最后一个数，它的右上没有数，这个可以不考虑，数组已经开出来了，不过得初始化为0)。从下往上就不用考虑这么多了。其实考虑到这，基本也差不多了，但是似乎我们得开一个二维数组来存这些结果，可是对于这些结果我们用不着都存起来，当我们考虑到第i行时，我们只要考虑第i-1行就行了，第i-1行以前的所有结果我们都没必要存起来。那么我们就可以用两个一维数组存起来了一个是当前行的最优结果(也就是要算的)，还有一个是上一行的最优结果。另外在
01背包里面会用到这样的优化，有时不优化就会MLE。(代码建议自己想先，再参考)
贴一下从下往上算的：
CODE
1/**//*
2
ID:qcx97811
3 LANG:C
4 PROG:numtri
5
*/
6
#include <stdio.h>
7#include <stdlib.h>
8#include <string.h>
9int num[1002][1002];
10int dp[1002][1002];
11int max_int(int a,int b)
12
{
13 return a > b ? a:b;
14}
15int main(main)
16{
17 freopen("numtri.in","r",stdin);
18 freopen("numtri.out","w",stdout);
19 int r;
20 int i,j;
21 scanf("%d",&r);
22 for(i = 0;i < r;i++)
23
{
24 for(j = 0;j <= i;j++)
25 scanf("%d",&num[i][j]);
26
}
27 memset(dp,0,sizeof(dp));
28 for(i = 0;i < r;i++)
29 dp[r-1][i] = num[r-1][i];//初始化最后一行的最优解
30 for(i = r-2;i >= 0;i--)
31 {
32 for(j = 0;j <= i;j++)
33 {
34 dp[i][j] = num[i][j] + max_int(dp[i+1][j],dp[i+1][j+1]);//每一行的最优解由它的左下和右下两个得到
35 }
36 }
37 printf("%d\n",dp[0][0]);//最终结果存在第一个元素中，也就是最上面的那个
38 return 0;
39}
40下面的代码是官方给的(省内存)
CODE2
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <assert.h>
5
6#define MAXR 1000
7
8int
9max(int a, int b)
10{
11 return a > b ? a : b;
12}
13
14void
15main(void)
16{
17 int best[MAXR], oldbest[MAXR];//best是当前行的最优值,oldbest
18//数组是当前行的上一行的最优值
19 int i, j, r, n, m;
20 FILE *fin, *fout;
21
22 fin = fopen("numtri.in", "r");
23 assert(fin != NULL);
24 fout = fopen("numtri.out", "w");
25 assert(fout != NULL);
26
27 fscanf(fin, "%d", &r);
28
29 for(i=0; i<MAXR; i++)
30 best[i] = 0;
31
32 for(i=1; i<=r; i++) {
33 memmove(oldbest, best, sizeof oldbest);//把上一次的最优结果赋值到这次的上一行最优结果中
34 for(j=0; j<i; j++) {
35 fscanf(fin, "%d", &n);
36 if(j == 0)//如果是每行的开头
37 best[j] = oldbest[j] + n;
38 else
39 best[j] = max(oldbest[j], oldbest[j-1]) + n;
40 }
41 }
42
43 m = 0;
44 for(i=0; i<r; i++)//在最后一行查找最优值
45 if(best[i] > m)
46 m = best[i];
47
48 fprintf(fout, "%d\n", m);
49 exit(0);
50}
51