用C++实现动态规划法求解数塔问题

数塔问题是指有一个由数字组成的三角形，从顶点开始向下走，每次只能向左下或右下走，直到走到底层，求从顶点到底层的最大路径和。以下是C++实现动态规划法求解数塔问题的代码：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
int dp[MAXN][MAXN];

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> dp[i][j];
        }
    }

    for (int i = n-1; i >= 1; i--) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]);
        }
    }

    cout << dp[1][1] << endl;

    return 0;
}

首先读入数塔的高度n，然后读入数塔的数据，存储在dp数组中。接着从倒数第二行开始，遍历每个数字，将其加上下一行相邻的两个数字中的较大值，更新dp数组。最后dp[1][1]就是最大路径和