1195: 零起点学算法102——数塔（动态规划）

蔚落 2022-10-25 05:58 243阅读 0赞

## Description ##

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：  
  
有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？  
![79b65092734d6a263a9280f5b332c5b9.png][]  
已经告诉你了，这是个DP的题目，你能AC吗?

## Input ##

输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间\[0,99\]内。

## Output ##

对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。

## Sample Input ![5f8f312f51791b8bb0ed0ae07c2ffa43.gif][] ##

1
    5
    7
    3 8
    8 1 0 
    2 7 4 4
    4 5 2 6 5

## Sample Output ##

## Source ##

[零起点学算法][Link 1]

## Code ##

如果自顶向下看的话，从7开始，下一步的选择取决于哪条路带来的最终结果更大，在下一层继续考虑，一层层向下最后问题归结到了最后一层的选择上，因此本题是自顶向下分析，自底向上计算。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2NTU5Nw_size_16_color_FFFFFF_t_70][]

将最后一层与倒数第二层相邻两两最大和的值存放在倒数第二层，即将倒数第二层的值更新，以此类推，到最后一层只有一个元素时，那个元素即为最大和

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    using namespace std;
    int main()
    {
        int c;
        cin>>c;
        while(c--)
        {
            int n;
            cin>>n;
            int tower[999][999];
            for(int i=1;i<=n;i++)
                for(int j=1;j<=i;j++)
                    cin>>tower[i][j];
            for(int i=n-1;i>0;i--)
            {
                for(int j=1;j<=i;j++)
                {
                    if((tower[i][j]+tower[i+1][j])>=tower[i][j]+tower[i+1][j+1])
                        tower[i][j]+=tower[i+1][j];
                    else
                        tower[i][j]+=tower[i+1][j+1];
                }
            }
            cout<<tower[1][1]<<endl;
        }
    }

上面的代码还有一个很愚蠢的地方，就是比较大小的时候直接比较tower\[i+1\]\[j\]和tower\[i+1\]\[j+1\]就好了，为啥要比较和....智商下线

[https://blog.csdn.net/hjf1201/article/details/78598744?utm\_medium=distribute.pc\_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.baidujs&depth\_1-utm\_source=distribute.pc\_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.baidujs][https_blog.csdn.net_hjf1201_article_details_78598744_utm_medium_distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.baidujs_depth_1-utm_source_distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.baidujs]

正确代码如下

#include <stdio.h>
    
    int main() {
        int M, i, j, N;
        int a[101][101];
        while (scanf("%d", &M) != EOF) {
            while (M--) {
                scanf("%d", &N);
                for (i = 0; i < N; i++)
                    for (j = 0; j <= i; j++)
                        scanf("%d", &a[i][j]);
                for (i = N - 1; i>=0; i--) {
                    for (j = 0; j <= i; j++) { //DP算法就不多解释了
                        if (a[i][j] + a[i-1][j] > a[i][j+1] + a[i-1][j])
                            a[i-1][j] = a[i][j] + a[i-1][j];
                        else
                            a[i-1][j] = a[i][j+1] + a[i-1][j];
                    }
                }
                printf("%d\n", a[0][0]);
            }
        }
        return 0;
    }

[79b65092734d6a263a9280f5b332c5b9.png]: /images/20221024/681e33ff3d1e48ac955631e7bc77ac64.png
[5f8f312f51791b8bb0ed0ae07c2ffa43.gif]: /images/20221024/badcb30eadc14bba8bff8e2f4f791ace.png
[Link 1]: https://oj.wustacm.top/problemset.php?search=%E9%9B%B6%E8%B5%B7%E7%82%B9%E5%AD%A6%E7%AE%97%E6%B3%95&searchmode=source&soj=0
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2NTU5Nw_size_16_color_FFFFFF_t_70]: /images/20221024/9b0d845a222645d1847d18c1addb0353.png
[https_blog.csdn.net_hjf1201_article_details_78598744_utm_medium_distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.baidujs_depth_1-utm_source_distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.baidujs]: https://blog.csdn.net/hjf1201/article/details/78598744?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.baidujs&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.baidujs