王道机试指南 例题12.10 The Triangle

题目：

题目大意：

算法及思路：

动态规划。

代码：

#include <iostream>

using namespace std;

int main(){
    int n;
    cin>>n;
    int matrix[n][n],dp[n][n];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            matrix[i][j]=0;
            dp[i][j]=0;
        }

    for(int i=0;i<n;i++)
        for(int j=0;j<i+1;j++)
            cin>>matrix[i][j];

    for(int i=n-1;i>=0;i--)
        for(int j=0;j<n;j++){
            if(i==n-1)//底部dp初始化为对应点自身值
                dp[i][j]=matrix[i][j];
            else//其他位置用状态转移方程求解
                dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+matrix[i][j];
        }

    cout<<dp[0][0]<<endl;
    return 0;
}

运行结果：