数字三角形（很经典的动态规划问题）

题目描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数 n，表示数字三角形的层数。

接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

1≤n≤500,

−10000≤三角形中的整数≤10000

输入样例：

1. 5
2. 7
3. 3 8
4. 8 1 0
5. 2 7 4 4
6. 4 5 2 6 5

输出样例：30

思路分析：

在分析状态集合的时候，可以发现如果f(i,j)是自顶向下遍历，那就有很多边界问题需要处理，因为下一层的f(i,j)可以由f(i-1,j-1)和f(i-1,j)递推。而如果是自底向上遍历就不需要考虑边界问题。这里是因为自底向上是层数越来越小（不需要考虑边界），自顶向下层数越来越大（需要考虑边界）

输入三角形：首先，我们需要读取输入的三角形数据，将其存储在一个二维数组中。

初始化：由于三角形的底层只有一个路径，所以底层的每个数字就是其自身的最大路径和。

自底向上计算：对于底层以上的每一层，我们从左到右遍历每个数字。对于当前层的每个数字，我们计算通过它的最大路径和，这可以通过比较它左下方和右下方的数字的最大路径和，然后将这个值加上当前数字的值来实现。

状态转移方程：对于第  i 行的第  j 个数字 T[i][j]，其最大路径和可以通过以下状态转移方程计算：  T[i][j]=T[i][j]+max(T[i+1][j],T[i+1][j+1])

返回顶部值：最后，三角形顶部的数字将包含通过它的所有可能路径的最大和，这就是我们需要的答案。

完整代码（很简洁）：

#include <iostream>
using namespace std;
const int N=510;
int dp[N][N];
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;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];
}

带注释：

#include <iostream>
using namespace std;
 
const int N = 510;  // 定义常量 N 为 510，表示数字三角形的最大层数
 
int dp[N][N];  // 定义二维数组 dp，用于存储动态规划中的状态值
 
int main() {
    int n;  // 声明变量 n，用于存储数字三角形的层数
    cin >> n;  // 读取输入的层数
 
    // 循环读取输入的每一行数据，并存储到二维数组 dp 中
    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] 表示第 i 行第 j 列位置的最大路径和
            // 更新 dp[i][j] 为当前位置值加上下一行相邻两个位置中的较大值
            dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]);
        }
    }
 
    // 输出结果，即在第一行第一列的位置上的最大路径和
    cout << dp[1][1];
 
    return 0;
}

总结：

通过解决这个“最大路径和问题”，我们可以获得一些关于动态规划和问题解决技巧的经验：

理解问题：首先，彻底理解问题的要求是至关重要的。在这个例子中，我们需要找到一条路径，使得路径上的数字和最大。

识别最优子结构：这个问题具有最优子结构，即一个子问题的解决方案可以被用来构建更大问题的解决方案。在这里，一个数字的最大路径和取决于它下方的两个数字的最大路径和。

状态转移方程：确定状态转移方程是动态规划的核心。在这个例子中，状态转移方程是当前数字的最大路径和等于当前数字加上它下方两个数字中的最大路径和。

记忆化：虽然在这个特定问题中没有直接使用记忆化（也称为自顶向下的动态规划），但这是动态规划的另一个重要方面。记忆化可以避免重复计算相同的子问题，提高算法效率。

自底向上的方法：从三角形的底层开始计算，逐步向上直到顶层，这是一种自底向上的思考方式，它有助于确保所有必要的信息都已经计算出来。

数据结构的选择：选择合适的数据结构来存储和更新计算结果。在这个问题中，二维数组是存储三角形和计算结果的自然选择。

边界条件的处理：在动态规划中，正确处理边界条件是至关重要的。在这个例子中，三角形的底层是边界条件，因为它们没有子节点。

递归与迭代：虽然动态规划通常与递归关联，但迭代方法（如自底向上的方法）在某些情况下更高效，因为它避免了递归调用的开销。

调试和测试：在实现算法后，进行彻底的测试以确保算法的正确性。测试不同的输入情况，包括边界情况。

优化：考虑算法的时间和空间复杂度，并寻找可能的优化方法。在这个问题中，由于我们只需要上一行的信息来计算当前行，因此可以通过只存储上一行的信息来减少空间复杂度。