三角形c++动态规划

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

#include<utility>

#include<map>

using namespace std;

long long dp[105][105];

long long num[105][105];

int main(){

int T,N;

cin>>T;

while(T--){

memset(dp,0,sizeof(dp));

scanf("%lld",&N);

for(int i=0;i<N;i++){

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

scanf("%lld",&num[i][j]);

}

}

dp[0][0]=num[0][0];

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

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

if(j==0){

dp[i][j]+=dp[i-1][j]+num[i][j];

}else{

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

}

}

}

long long maxn=dp[N-1][0];

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

if(dp[N-1][i]>maxn){

maxn=dp[N-1][i];

}

}

cout<<maxn<<endl;

} 

return 0;

}