The Triangle 动态规划
#include<bits/stdc++.h>
using namespace std;
const int Max=1000;
int a[Max][Max];
int dp[Max][Max];
int main(){
int n;
while(cin>>n){
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
cin>>a[i][j];
dp[i][j]=a[i][j];
}
}
for(int i=n-2;i>=0;--i){
for(int j=0;j<=i;j++){
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
}
}
cout<<dp[0][0]<<endl;
}
return 0;
}
using namespace std;
const int Max=1000;
int a[Max][Max];
int dp[Max][Max];
int main(){
int n;
while(cin>>n){
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
cin>>a[i][j];
dp[i][j]=a[i][j];
}
}
for(int i=n-2;i>=0;--i){
for(int j=0;j<=i;j++){
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
}
}
cout<<dp[0][0]<<endl;
}
return 0;
}
查看19道真题和解析
