IOI 1994 洛谷1216：如何用动态规划高效解决数字三角形问题？附完整代码解析

题目重解

给定一个由数字组成的三角形结构，从顶部出发，每次可以移动到下方相邻的数字，最终到达底部。我们的目标是找到一条路径，使得路径上经过的数字总和最大。这个问题在实际中有许多应用场景，如最优路径规划、资源分配等。

解题思路

1.首先读取数字三角形并存储在二维数组中

2.初始化dp数组，dp[i][j]表示到达第i行第j列时的最大和

3.对于每个位置，考虑从左上或右上转移过来的可能：

        1.第一列只能从正上方转移

        2.最后一列只能从左上方转移

        3.中间位置取上方两个位置中的较大值

        4.最后遍历最后一行找出最大值

代码详解

#include<iostream>
using namespace std;

int main()
{
    int r;  // 三角形行数
    cin>>r;
    // 申请存储三角形数字和dp数组的空间
    int** num=new int*[r];
    int** dp=new int*[r];
    for(int i=0;i<r;i++){
        dp[i]=new int[r];
        num[i]=new int[r];
        // 读取每行数字
        for(int j=0;j<=i;j++)
            cin>>num[i][j];
    }
    
    // 初始化起点
    dp[0][0]=num[0][0];
    // 动态规划过程
    for(int i=1;i<r;i++){
        for(int j=0;j<=i;j++){
            if(!j) dp[i][j]=dp[i-1][j]+num[i][j];  // 最左列
            else if(j==i) dp[i][j]=dp[i-1][j-1]+num[i][j];  // 最右列
            else dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+num[i][j];  // 中间位置
        }
    }
    // 找出最后一行最大值
    int ret=0;
    for(int i=0;i<r;i++)
        ret=max(ret,dp[r-1][i]);
    cout<<ret;
    
    // 释放内存
    for(int i=0;i<r;i++){
        delete[] dp[i];
        delete[] num[i];
    }
    delete[] dp;
    delete[] num;
    return 0;
}