数塔 - 源码之家

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

已经告诉你了，这是个DP的题目，你能AC吗?

Input输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。
Output对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。
Sample Input

Sample Output

这个题是一道比较典型的动态规划题。首先肯定是设一个N*N的二维数组存数据。刚开始思考的时候想着从上到下，但怎么也想不出办法，后来看了大神的代码才想起来可以倒着循环很简单的得出最优解。第一步倒数第二行的每一个与下面配对的两个分别进行配对比较，然后将最后两行替换成一行的和。依次类推，最后二维数组的第一个便是得到的最优解。代码如下：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int j,i,n,m;
    long long int a[105][105];
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=i;j++)
            {
                scanf("%I64d",&a[i][j]);
            }
        }
        for(i=n-1;i>=1;i--)
        {
            for(j=1;j<=i;j++)
            {
                if(a[i][j]+a[i+1][j]>a[i][j]+a[i+1][j+1])
                    a[i][j]=a[i][j]+a[i+1][j];
                else a[i][j]=a[i][j]+a[i+1][j+1];
            }
        }
        printf("%I64d\n",a[1][1]);
    }
    return 0;
}

数塔

相关推荐