数塔

采用记忆化搜索与dp分开写，两种实现方法的本质差不多
 1 #include<time.h>
 2 #include <cstdio>  
 3 #include <iostream>  
 4 #include<algorithm>
 5 #include<math.h> 
 6 #include <string.h>  
 7 #include<vector> 
 8 #include<queue>
 9 using namespace std;
10 
11 int dp[1005][1005],map[1005][1005];
12 int n;
13 
14 
15 //记忆化搜索 124MS    5924K
16 
17 int solve(int i,int j)
18 {
19     if(dp[i][j]>=0) //如果大于0则一定是已经被访问过的 
20         return dp[i][j];
21     return dp[i][j]=map[i][j]+(i==n? 0:max(solve(i+1,j),solve(i+1,j+1)));//注意判断边界值 
22 }
23 
24 int main()
25 {
26     int cas;
27     scanf("%d",&cas);
28     while(cas--)
29     {
30         scanf("%d",&n);
31         for(int i=1;i<=n;i++)
32             for(int j=1;j<=i;j++)
33                 scanf("%d",&map[i][j]);
34         
35         memset(dp,-1,sizeof(dp)); //标记为-1 
36         
37         printf("%d
",solve(1,1)); 
38     }
39     return 0;
40 }
41 
42 
43 
44 // 动态规划代码 124MS    5920K
45 int main()
46 {
47     int cas;
48     scanf("%d",&cas);
49     while(cas--)
50     {
51         scanf("%d",&n);
52         for(int i=1;i<=n;i++)
53             for(int j=1;j<=i;j++)
54                 scanf("%d",&map[i][j]);
55         
56         memset(dp,0,sizeof(dp));
57         
58         for(int i=n;i>=1;i--)//自下而上计算 
59             for(int j=1;j<=i;j++)
60                 dp[i][j]=map[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
61         
62         printf("%d
",dp[1][1]); 
63     }
64     return 0;
65 }