数塔问题（dp入门）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2084

题意：有一个数塔，求从塔顶走到塔底的最大路径和

dp思想：我们要用dp[n][n]来存储从第1层到第i层的最大路径和 ； 1是必须经过的；-》到第二层就是3和4；-》第三层就是7和9和10...   总是可以的出第i到第i+1层     共i+1个最大值； 直到最后一层求n个最优值中的最大值；

#include<iostream>
#include<cstdlib>
#include<cstring> 
using namespace std;
int dp[105][105];
int arr[105][105];
int main(){
	memset(dp,0,sizeof(dp));
	memset(arr,0,sizeof(arr));
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>arr[i][j];
		}
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+arr[i][j];			
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(dp[n][i],ans);
	}
	cout<<ans;
    return 0;
} 

后记：今天写AcWing的题，发现整数取值在-1000~1000 会出现负数右边界问题，对第一列和i=j(在对角线上)的会出现问题

解决办法：初始化dp[i][j]数组

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=505, INF=1e9;
int g[N][N];
int f[N][N];
int main(){
    int n; cin>>n;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            f[i][j]=-INF;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>g[i][j];
        }
    }
    f[1][1]=g[1][1];
    for(int i=2; i<=n;i++){
        for(int j=1;j<=i; j++){
            f[i][j]=max(f[i-1][j],f[i-1][j-1])+g[i][j];
        }
    }
    int res=-2e9;
    for(int i=1;i<=n;i++) res=max(res,f[n][i]);
    cout<<res<<endl;
    return 0;
}

最后

以上就是激昂发箍为你收集整理的数塔问题（dp入门）的全部内容，希望文章能够帮你解决数塔问题（dp入门）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。