有名的数塔问题,对于刚接触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>
9
int num[1002][1002];
10
int dp[1002][1002];
11
int max_int(int a,int b)
12

{
13
return a > b ? a:b;
14
}
15
int 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
8
int
9
max(int a, int b)
10

{
11
return a > b ? a : b;
12
}
13
14
void
15
main(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