//
动态规划
从底向上的对路线进行求最大值计算
将dp[i][j]的值定义为由底部到达点(i,j)的最大值,其最大值的来源可以分为两部分
1.由左下方的最大值通过w[i][j]到达点(i,j) 2.由右下方的最大值通过w[i][j]达到点(i,j)
将这两个最大值进行比较,就可以获得点(i,j)处的最大值 即dp[i][j]
include “iostream”
using namespace std;
const int N=500;
int w[N][N],dp[N][N];
int n;
int max(int a,int b){
return a>b? a:b;
}
void DP(){
for (int i=1;i<=n;i++){
dp[n][i]=w[n][i];
}
for (int i=n-1;i>0;i--){
for (int j=1;j<=i;j++){
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+w[i][j];
}
}
int main(){
cin>>n;
for (int i=1;i<=n;i){
for (int j=1;j<=n;j){
cin>>w[i][j];
}
}
DP();
cout<<dp[1][1]<<endl;
return 0;
}