请问这道数字三角形如何理解呢？

Question

请问这道数字三角形如何理解呢？有四段代码，我不是很懂，希望大家帮注释一下代码并讲一下思路。非常感谢！

#include<iostream>
#include<cstdio>
usning namespace std;

#define MAX_NUM 100
int d[MAX_NUM + 10][MAX_NUM + 10];
int N;

int MaxSum(int r, int j)
{
    if (r == N）
        return d[r][j]
        int sum1 = MaxSun(r + 1, j);
        int sum2 = MaxSum(r + 1, j + 1);
        if (sum1 > sum2)
            return sum1 + d[r][j]
            return sum2 + d[r][j];
}

int main()
{
    int m;
    scanf("%d", &N);
    for (int i = 1;i <= N;i++)
        for (int j = 1;j <= i;i++)
            scanf("%d", &d[i][j]);
    printf("%d", MaxSum(1, 1));
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define MAX_NUM 100
int d[MAX_NUM + 10][MAX_NUM + 10];
int N;
int maxSum[MAX_NUM + 10][MAX_NUM + 10];

int MaxSum(int r, int j)
{
    if (r == N)
        return d[r][j];
    if (maxSum[r + 1][j] == -1)
        maxSum[r + 1][j] = MaxSum(r + 1, j);
    if (maxSum[r + 1][j + 1] == -1)
        maxSum[r + 1][j + 1] = MaxSum(r + 1, j + 1);
    if (maxSum[r + 1][j] > maxSum[r + 1][j + 1])
        return maxSum[r + 1][j] + d[r][j];
}

int main()
{
    int m;
    scanf("%d", &N);

    memset(maxSum, -1, sizeof(maxSum));
    for (int i = 1;i <= N;i++)
        for (int j = 1;j <= i;j++)
            scanf("%d", &d[i][j]);
    printf("%d", MaxSum(1, 1))l
        return 0;
}

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

#define MAX_NUM 100
int d[MAX_NUM + 10][MAX_NUM + 10];
int N;
int maxSum[MAX_NUM + 10][MAX_NUM + 10];

int main()
{
    int i, j;
    scanf("%d", &N);
    for (i = 1, i <= N;i++)
        for (j = 1;j <= i;j++)
            scanf("%d", &d[i][j]);
    for (j = 1;j <= N;j++)
        maxSum[N][j] = d[N][j];
    for (i = N;i > 1;i--)
        for (j = 1;j < i;j++) {
            if (maxSum[i][j] > maxSum[i][j + 1])
                maxSum[i - 1][j] = maxSum[i][j] + d[i - 1][j];
            else
                maxSum[i - 1][j] = maxSun[i][j + 1] + d[i - 1][j];
        }
    printf("%d", maxSum[1][1]);
    return 0;
}

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

#define MAX 101
int D[MAX][MAX];
int n;int* maxSum;

int main() {
    int i, j;
    cin >> n;
    for (i = 1, i <= n;i++）
        for (j = 1;j <= i;j++)
            cin >> D[i][j];
        maxSum = D[n];
        for (int i = n - 1;i >= 1, --i)
            for (int j = 1;j <= i;++j)
                maxSum[j] = max(maxSum[j], maxSum[j + 1]) + D[i][j];
        cout << maxSum[1] << endl;
}

Answer 1

阅读、理解、注释、讲解四段代码的工作量非常大，很抱歉我无力完成。我仅分析一下第四段代码。
另外，我不建议你直接贴代码让别人来分析，而是应该首先理解书上作者的描述、逻辑，在脑海中构建出解题的思路。有必要的话自己跑代码，并且学会使用代码调试器观察程序运行途中变量的值，这样有便于你自己理解，也有利于你的编程思维。
我个人并不是很喜欢硬分析别人给出的代码，而是自己从头开始写，如果遇到什么困难再去看看别人在那个地方是怎么写的。

---

概括一下这四段代码别写了啥：
①代码一直接递归，时间开销O(2^N)为指数量级，耗时巨大；
②代码二叫备忘录式的动态规划。他建立了一个表格，标记了哪些路径已经算过了，哪些没有算过。算过的值就可以直接拿来用。这个算法已经把时间复杂度降低为O(N²)的多项式，改进巨大；
③代码三叫递推式的动态规划。他直接从子问题（更短的路径）开始解决，然后用子问题的答案直接求解更大的问题，逐步推进。递推式的动态规划比备忘录式的在时间复杂度上的常数更小，但是数量级依然是O(N²)的；
④代码四用了滚动数组的技巧，用新算出来的值覆盖掉老的、不再使用的值。此方法把空间复杂度从O(N²)降到O(N)，时间复杂度不变（已无法改进）。

---

动态规划中的状态转移方程非常重要，程序的核心就是在递推这个方程求值，顺带一点边角料的处理。本题的状态转移方程：

maxSum[r][j] =
{
    D[r][j], if r == N
    max{maxSum[r+1][j], maxSum[r+1][j+1]} + D[r][j], if r < N
}

在状态转移方程中，maxSum[r][j]指的是从三角形的最下面一行走到第r行第j个数字时的最大的和，D[r][j]指的是三角形中第r行第j个数字。
如果r == N，那么路径上仅有这个数字，故maxSum[r][j] = D[r][j]；
如果r < N，那么从D[r][j]这一点的左侧最大路径maxSum[r+1][j]和右侧最大路径maxSum[r+1][j+1]中选一个更大的，再加上D[r][j]本身的值，得到maxSum[r][j]的结果。

---

这是对第四段代码进行注释：

#include<iostream>
#include<algorithm>
using namespace std;
 
#define MAX 101
int D[MAX][MAX]; // 二维数组D，用于存储这个数字三角形。
int n; int* maxSum; // maxSum是一个int指针。
 
int main() {
    int i, j;
    cin >> n; // 将N存入变量n.
    for (i = 1, i <= n;i++）
        for (j = 1;j <= i;j++)
            cin >> D[i][j]; // 将数字三角形读入二维数组D.
    maxSum = D[n]; // 将maxSum指向三角形的最后一行，实现了状态转移方程中r == N时的情况。此时maxSum是个一维数组，maxSum[j]保存了第N行第j个位置的最大路径（从三角形最下行开始走）。
    for (int i = n - 1; i >= 1; --i) // 变量i是当前考虑的行数，从第n-1行递减到第1行。
        for (int j = 1; j <= i; ++j) // 考虑第i行第j个位置，从1递增到i，因为第i行只有i个数。
            maxSum[j] = max(maxSum[j], maxSum[j + 1]) + D[i][j]; // 实现状态转移方程r < N时的递推。这里算第i行的maxSum[j]时，使用了已经算好且存下来的第i+1行的maxSum[j]和maxSum[j+1]的值，并直接覆盖了maxSum[j]的值，这并不会干扰接下来对maxSum[j+1]的计算。这就是滚动数组的主要思想。
    cout << maxSum[1] << endl; // 输出结果。变量i最终的值为1，即maxSum当前存的是第1行的情况。
}