数字金字塔解题报告

用二维数组记录数，每一个数a[i][k]对应的下两个数是a[i+1][k]和a[i+1][k+1]
队列数组也可以

记忆化搜索

从下往上讨论
DP==从下往下讨论

DP, f[i][k]从塔顶到此处的最大路径
引申滚动数组

 1 #include <cstdio>
 2 using namespace std;
 3 #define maxr 1001
 4 int a[maxr][maxr];
 5 bool f[maxr][maxr];
 6 int r;
 7 int max(int a, int b)
 8 {
 9     if(a>b)    return a;
10     return b;
11 }
12 void dfs(int i, int k)
13 {
14     if(i==r)    return;
15     if(f[i+1][k]==0)
16     {
17         dfs(i+1, k);
18         f[i+1][k]=1;
19     }
20     if(k<=i&&f[i+1][k+1]==0)    
21     {
22         dfs(i+1, k+1);
23         f[i+1][k+1]=1;
24     }
25     a[i][k]+=max(a[i+1][k],a[i+1][k+1]);
26 }
27 int main()
28 {
29     int i, k;
30     scanf("%d", &r);
31     for(i=1; i<=r; i++)
32     {
33         for(k=1; k<=i; k++)
34         {
35             scanf("%d", &a[i][k]);
36         }
37     }
38     for(i=1; i<=r; i++)    f[r][i]=1;
39     dfs(1, 1);
40     printf("%d", a[1][1]);
41     return 0;
42 }

记忆化

 1 #include <cstdio>
 2 using namespace std;
 3 #define maxr 1001
 4 int max(int a, int b)
 5 {
 6     if(a>b)    return a;
 7     return b;
 8 }
 9 int a[maxr][maxr];
10 int main()
11 {
12     int r, i, k;
13     scanf("%d", &r);
14     for(i=1; i<=r; i++)
15     {
16         for(k=1; k<=i; k++)
17         {
18             scanf("%d", &a[i][k]);
19         }
20     }
21     for(i=r-1; i>=1; i--)
22     {
23         for(k=1; k<=i; k++)
24         {
25             a[i][k]+=max(a[i+1][k], a[i+1][k+1]);
26         }
27     }
28     printf("%d", a[1][1]);
29     return 0;
30 }

从下往上讨论

 1 #include <cstdio>
 2 using namespace std;
 3 #define maxr 1001
 4 int max(int a, int b)
 5 {
 6     if(a>b)    return a;
 7     return b;
 8 }
 9 int a[maxr][maxr];
10 int main()
11 {
12     int r, i, k, ans=0;
13     scanf("%d", &r);
14     for(i=1; i<=r; i++)
15     {
16         for(k=1; k<=i; k++)
17         {
18             scanf("%d", &a[i][k]);
19             a[i][k]+=max(a[i-1][k-1], a[i-1][k]);
20             ans=max(a[i][k], ans);
21         }
22     }
23     printf("%d", ans);
24     return 0;
25 }

DP, f[i][k]从塔顶到此处的最大路径

 1 #include <cstdio>
 2 using namespace std;
 3 #define maxr 1001
 4 int max(int a, int b)
 5 {
 6     if(a>b)    return a;
 7     return b;
 8 }
 9 int a[2][maxr];
10 int main()
11 {
12     int r, i, k, ans=0, ri, pi;
13     scanf("%d", &r);
14     for(i=1; i<=r; i++)
15     {
16         ri=i%2;
17         pi=!ri;
18         for(k=1; k<=i; k++)
19         {
20             scanf("%d", &a[ri][k]);
21             a[ri][k]+=max(a[pi][k-1], a[pi][k]);
22             ans=max(a[ri][k], ans);
23         }
24     }
25     printf("%d", ans);
26     return 0;
27 }

滚动数组