数塔问题

大概是室友被折磨的不清，跟我说Chatgpt都写不了，所以我就手写了一个，顺便感受了一下久违的动态规划思想

题目描述

一个高度为N的数塔由正整数数字三角形组成，即每往下一层，数字台阶多两个。从上走到下，每次只能走到下一层相邻的左，中，右三个台阶。例如，对于三角形：
5
984
56369
1837285
第二层的台阶4，只能走到下层的3，6，9台阶，不能走到5和6台阶。
数塔从上到下，一直到底层，走过便做数字累加，那么，所有可能路径中的数字和最大值是多少呢？例如，上例中的最大值是：5+9+6+8 = 28。
输入
若干数塔，每个数塔由一个整数n（n<=30）开始，后跟n行数字串，表示高为n的数塔。显然数字串每行以两个字符递增。
输出
对应每个数塔，以一行的格式输出路径最大值。

样例输入

2
3
235
4
5
984
56369
1837285

样例输出

8
28

这是个非常经典运用了动态规划思想的问题，那么问题来了。
动态规划是什么玩意

Q：什么是动态规划?
A：动态规划是一种解决多阶段决策过程最优化问题的思想，通常用于具有重叠子问题和最优子结构性质的问题。核心思想就是将原问题分解为若干个子问题，并通过求解每个子问题的最优解来得到原问题的最优解，明显区别于贪心算法。这里的“动态”指的是阶段之间的相互联系性，而“规划”则指的是策略的选择。
Q：状态转移方程是什么？
A：状态转移方程是将原问题的求解转化为子问题的求解时所用到的方程式。简单来说，就是用一系列的状态表示问题，并通过状态之间的转移关系来求解最优解。

仅以此题为例，其中具有很明显的阶段性——即从数塔的每一层前往下一层，这一过程可以进行明显拆分且不可逆
明确本题需要求解的是从数塔的顶端走到底端的最大数字总和
因此我们可以进行以下定义：dpi表示从数塔的第i行第j个数字出发直到底部的最大数字总和
可得动态转移方程

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

其中trianglei为存储了数塔的二维数组
由于每个dpi只依赖于下一行的状态，因此可以从下往上递推，得到最终答案。
所以思路明确：从最底层开始向上递推，最后输出dp0即为答案。

而由于本题数据的特殊性，所以我使用了一维字符串数组进行数塔的存储。

const int MAXN = 35;
int dp[MAXN][MAXN];
string a[MAXN];

读取数据

for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

初始化dp数组最后一行

for (int i = 0; i < a[n - 1].length(); i++) {
            dp[n - 1][i] = a[n - 1][i] - '0';
        }

使用状态转移方程计算每一层的dp，注意这里需要防止数组越界我铸币写错了符号

        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < a[i].length(); j++) {
                dp[i][j] = a[i][j] - '0' + max(dp[i + 1][j], max(dp[i + 1][j + 1], dp[i + 1][j + 2]));
            }
        }

最后完整代码如下

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 35;
int dp[MAXN][MAXN];
string a[MAXN];

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 35;
int dp[MAXN][MAXN];
string a[MAXN];

int main() {
    int n;
    while (cin >> n) {
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < a[n - 1].length(); i++) {
            dp[n - 1][i] = a[n - 1][i] - '0';
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < a[i].length(); j++) {
                dp[i][j] = a[i][j] - '0' + max(dp[i + 1][j], max(dp[i + 1][j + 1], dp[i + 1][j + 2]));
            }
        }
        cout << dp[0][0] << endl;
    }
    return 0;
}