1数塔问题问题描述

数塔问题是一道经典的动态规划问题，其描述如下：给定一个由n行数字组成的数塔，第i行有i个数字，如下图所示：

    9
   12 15
  10  6  8
 2  18  9  5

从数塔的顶部走到底部，每次只能向下走相邻的两个数字，求出一条从顶部到底部的路径，使得路径上经过的数字之和最大。

例如，在上面的数塔中，从顶部到底部经过的数字之和最大的路径为9->15->8->18，其路径上的数字之和为50。

2.数塔问题解法

数塔问题可以使用动态规划来解决。具体地，我们可以定义一个二维数组dp，其中dp[i][j]表示从数塔的第i行第j个数字开始，到底部的最大路径和。则dp[1][1]即为最终的答案。

对于dp[i][j]，其可以由dp[i+1][j]和dp[i+1][j+1]转移而来，即：

dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + a[i][j]

其中a[i][j]表示数塔的第i行第j个数字。

最终的答案即为dp[1][1]。

代码实现如下：

int dp[MAXN][MAXN];
int a[MAXN][MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= i; j++) {
            if (i == n) dp[i][j] = a[i][j];
            else dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + a[i][j];
        }
    }
    cout << dp[1][1] << endl;
    return 0;
}
``