动态规划（入门级）-数塔

我就是我 2022-05-15 03:13 189阅读 0赞

## 题目：      ##

##                                                   数塔 ##

## 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 ##

## 思路： ##

## 自底向上，逐步求解。 ##

数塔倒数第二层开始，max(dp\[i+1\],dp\[i+1\]\[j+1\] )就是下一层的最优解，用dp\[i\]\[j\]存储，每一步的最优解，从下往上递推，dp\[0\]\[0\]一定是最大的。

### 动态方程：dp\[i\]\[j\]=max(dp\[i+1\]\[j\],dp\[i+1\]\[j+1\]) ###

## 代码： ##

#include <bits/stdc++.h>
    using namespace std;
    #define L 100
    int main()
    {
        int t,n,a[L][L];
        cin>>t;
        while(t--)
        {
            cin>>n;
            for(int i=0; i<n; i++)
                for(int j=0; j<=i; j++)
                    cin>>a[i][j];
            for(int i=n-2; i>=0; i--)
                for(int j=0; j<=i; j++)
                {
                    a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
                }
            cout<<a[0][0]<<endl;
        }
        return 0;
    }

[2084-1.jpg]: /images/20220515/69a159a9d5c34bb085fd1eaba70a72e9.png