C++ 动态规划,反向从下往上计算.

解题思路:动态规划,将输入的三角形数值存入数组,由题意:每一步只能由当前位置向左下或右下可得在数组中只能从下或右下走,因此从倒数第二行(倒数第一行下面没有元素)元素dp[i][j]计算时,dp[i][j]=dp[i][j]+max(dp[i+1][j],dp[i+1][j+1])即本身的值加下与右下值中最大的.以此类推第一个元素dp[0][0]的值就是所求最大路径的值.

注意事项:动态规划,数组,从下往上

参考代码:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,line,i,j;
    cin>>n;
    while(n--){
        cin>>line;
        vector<vector<int>> trangle(line,vector<int>(line,0));//初始化数组
        for(i=0;i<line;i++){
            for(j=0;j<=i;j++){
                cin>>trangle[i][j];//给三角形对应位置赋值
            }
        }
        for(i=line-2;i>=0;i--){
            for(j=0;j<=i;j++){
                trangle[i][j]+=max(trangle[i+1][j],trangle[i+1][j+1]);//当前值加等于下方和右下方元素当中的最大值
            }
        }
        cout<<trangle[0][0]<<endl;
    }
    return 0;
}