一个简单的dp题,
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
结果是30
下面的代码可以通过,但是如果把两行数组声明放入主函数里就没有结果了,用的是devc++5.4.0
#include<bits/stdc++.h>
using namespace std;
int mp[1005][1005];// 这两行放到主函数里没有结果
int dp[1005][1005];//
int main(){
int r;
freopen("sanjiao.txt","r",stdin);
cin>>r;
for(int i=0;i<r;i++){
for(int j=0;j<=i;j++){
cin>>mp[i][j];
}
dp[0][0]=mp[0][0];
if(i>0) {
dp[i][0]=mp[i][0]+dp[i-1][0];
dp[i][i]=mp[i][i]+dp[i-1][i-1];
}
}
for(int i=2;i<r;i++){
for(int j=1;j<i;j++){
dp[i][j]=mp[i][j]+max(dp[i-1][j],dp[i-1][j-1]);
}
}
int ans=0;
for(int i =0;i<r;i++){
ans=max(dp[r-1][i],ans);
}
cout<<ans;
return 0;
}