IOI 1994 洛谷1216：如何用O(1)空间解决数字三角形问题？附代码实现

题目重解：

数字三角形是一个经典的动态规划问题，给定一个由数字组成的三角形结构，从顶部出发，每次可以移动到下方相邻的数字，最终到达底部。我们需要找到一条路径，使得路径上经过的数字总和最大。这个问题可以很好地展示动态规划的空间优化技巧。

解题思路：

1.直接在原数组上进行操作，不需要额外空间

2.从倒数第二行开始向上处理

3.每个位置更新为当前值加上下方两个相邻位置中的较大值

4.最终顶部元素即为最大路径和

这种方法将空间复杂度优化到O(1)，直接在输入数组上进行修改，是最优的空间解决方案。

代码详解：

#include<iostream>
using namespace std;
int** nums; // 定义一个二维指针数组，用于存储数字三角形

int main()
{
    int r; // 三角形的行数
    cin>>r; // 输入行数
    nums=new int*[r]; // 为每一行分配指针空间
    for(int i=0;i<r;i++){
        nums[i]=new int[r]; // 为每一行分配具体的存储空间
        for(int j=0;j<=i;j++) // 逐行输入数字
            cin>>nums[i][j];
    }
    for(int i=r-1;i>0;i--){ // 从倒数第二行开始向上计算
        for(int j=0;j<r;j++){ // 遍历当前行的每个位置
            nums[i-1][j]+=max(nums[i][j],nums[i][j+1]); // 更新当前位置的最大路径和
        }
    }    
    cout<<nums[0][0]; // 输出顶部的最大路径和，即为最终答案

    return 0;
}