数塔问题

系统管理员 2022-06-01 02:40 211阅读 0赞

[数塔][Link 1]

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

解析：  
这题算是dp的入门题，采用动态规划自底向上计算，如果我们要知道所走之和最大，那么最后一步肯定是走最后一排数其中一个，向上退，倒数第二步肯定走最后一排数对应的倒数第二排最大的一个（将最后对应最后步走的最大的数加起来存在倒数第二步的数组中）再向上推，一直推到最上面的第0步，那么dp\[0\]\[0\]最后所存的结果一定是最大的。

代码：

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<algorithm>
    #define max(a,b) ((a)>(b)?(a):(b));
    using namespace std;
    int N,sum;
    int a[101][101],b[101][101];
    int main()
    {
        int test;
        scanf("%d",&test);
        while(test--)
        {
            int i,j;
            scanf("%d",&N);
            for(i=0; i<N; i++)
            {
                for(j=0; j<=i; j++)
                {
                    scanf("%d",&a[i][j]);
                    b[i][j]=a[i][j];
                }
            }
            for(int i=N-2; i>=0; i--)
                for(int j=0; j<=i; j++)
                {
                    b[i][j]+=max(b[i+1][j],b[i+1][j+1]); //最关键的式子，父节点的值加上子节点中较大一个的值。
                }
            printf("%d\n",b[0][0]); //最后要求的最大值。
        }
        return 0;
    }

[Link 1]: http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=23620
[2084-1.jpg]: /images/20220601/ba0616e18b944c948c4c087191a8b04f.png