数字三角形问题 动态规划

#include<iostream>

using namespace std;



int main(){

    //输入的数组

    int arr[100][100];

    //表示距离的数组

    int max[100][100]={0};

    //输入三角形的行数

    int length;

    cin>>length;

   //逐个输入元素

   for(int i=1;i<=length;i++){

       for(int j=1;j<=i;j++){

           cin>>arr[i][j];

           if(i==length){

               //最底层的最大路径是本身 

           max[i][j]=arr[i][j]; 

       }

   } 

   } 

   //从底层开始递推

  for(int j=length-1;j>=1;j--){

      for(int i=1;i<=length-1;i++){

          //正下方 

          int one=max[j+1][i];

          int two=max[j+1][i+1];

        if(one>=two){

            max[j][i]=one+arr[j][i]; 

         } else{

             max[j][i]=two+arr[j][i] ; 

          } 

      } 

  } 

  cout<<max[1][1]<<endl;

   

}