题解 | 数字三角形

读三角形进二维数组，由题可知三角形第n行有n个数，所以行的下标等于该行数字个数。

做dp二维数组，初始化置零。

每行首位数字仅需要考虑它的上一行的首位数字，所以当循环到第一列时用上一行首位加上当前数字；

每行末尾数字仅需要考虑它的上一行的末尾数字，所以当循环到最后一列时用上一行末尾位加上当前数字；

中间数字需要考虑上一行的两个数(位于当前数字上方的两个数)，所以取最大的那个加上当前数字。

状态转移方程：

dp[i][j]=dp[i-1][j]+v[i][j] j==1

dp[i][j]=dp[i-1][j-1]+v[i][j] j==i

dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+v[i][j]; other

最后遍历最后一行的最大数即为最佳路线的结果。

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

int main() {
    int n;
    cin>>n;
    vector<vector<int>> tri(n+1,vector<int>(n+1));
    vector<vector<int>> dp(n+1,vector<int>(n+1,0));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=i;++j){
            cin>>tri[i][j];
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=i;++j){
            if(j==1){
                dp[i][j]=dp[i-1][j]+tri[i][j];
            }else if(j==i){
                dp[i][j]=dp[i-1][j-1]+tri[i][j];
            }else{
                dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+tri[i][j];
            }
        }
    }
    int ans = dp[n][1];
    for(int i=1;i<=n;++i) ans = max(dp[n][i],ans);
    cout<<ans;
}