新手初次练习DP不知道错误在哪里==

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

Input:

输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。

Output:

对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。

#include <iostream>
#include <memory.h>
using namespace std;
int N,tri[100][100];
int top(int i,int j){
	if(i==N-1){
		return tri[i][j];
	}else{
		for(int t=0;t<=i;t++){
			int a=top(i+1,t);
			int b=top(i+1,t+1);			
			return (a>b)?(a+tri[i][t]):(b+tri[i][t]);
		}
	}
		
}
int main(){
	int C;
	cin>>C;
	while(C--){
		cin>>N;
		memset(tri,0,sizeof(tri));
		int i=0;
		while(i<N){
			for(int j=0;j<=i;j++){
				cin>>tri[i][j];
			}
			i++;
		}
		cout<<top(0,0)<<endl;
	}
}

想尝试使用二元数组，然后悲剧了，不知道哪里逻辑不对，求大神指点^^

全部评论

推荐最新楼层

已删除

循环♻多了，一般一个递归、一个建表两种方法最好都会

点赞回复分享

发布于 2017-08-12 10:28

小伟成

美团_Java研发工程师

从下到上每层计算通项公式 top(m,n)=max(top(m+1,n),top(m+1,n+1)+tree[m][n],最底层时top(m,n)=tree[m][n],最好用一位数组存储中间结果,

点赞回复分享

发布于 2017-08-12 01:22

浮生一梦暗若痴

老和山职业技术学院 C++

top函数错了，改成下面的样子。 int top(int i,int j){ if(i==N-1){ return tri[i][j]; }else{ int a=top(i+1,j); int b=top(i+1,j+1); return (a>b)?(a+tri[i][j]):(b+tri[i][j]); } } 另外你这样做会有很多重复的计算，应该用一个二维数组存储计算过的节点。下面是我刚刚写的，比较大众的做法（我也是弱鸡，代码丑别笑我 =￣ω￣= #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <climits> using namespace std; int main(){ int N; cin>>N; while(N--){ int n; cin>>n; int a[n+1][n]; // 这里dp数组本应为dp[n+1][n] // 因为第i层的状态仅由i-1层决定 // 为了节省空间，所以仅分配了两层 int dp[2][n]; memset(dp,0,sizeof dp); for(int i=1;i<=n;++i){ for(int j=0;j<n;++j){ cin>>a[i][j]; } } int las(0),cur(1); dp[las][0] = a[1][0]; for(int i=2;i<=n;++i){ for(int j=0;j<i;++j){ if(j-1<0){ dp[cur][j] = dp[las][j]+a[i][j]; }else if(j+1>=i){ dp[cur][j] = dp[las][j-1]+a[i][j]; }else{ dp[cur][j] = max(dp[las][j],dp[las][j-1])+a[i][j]; } } swap(las,cur); } int res = INT_MIN; for(int i=0;i<n;++i){ res = max(res,dp[las][i]); } cout<<res<<endl; } }

点赞回复分享

发布于 2017-08-12 01:08