数塔问题求解--动态规划

题目描述 

如下图，找寻从第一个结点5到最后一层结点的最长路径（即结点数和最大），图片是自己用画图画的，凑合看吧。

解题思路

典型的动态规划问题，也可以用递归来算，但是会炒鸡慢，这里直接用动态规划来求解。

#include<iostream>
#include<string.h> 
using namespace std;
const int MAXLENGTH=100;
int F[MAXLENGTH][MAXLENGTH];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			int temp;
			cin>>temp;
			F[i][j]=temp;
		}
	}
	int dp[n+1][n+1];	//dp[i][j]表示到达塔第i行第j列的最长路径长度 
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		dp[n][i]=F[n][i];
	}
	for(int i=n-1;i>=1;i--){
		for(int j=1;j<=i;j++){
			dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+F[i][j];
		}
	}
	cout<<dp[1][1]<<endl;
	return 0;
}
/*输入示例：
5
5
8 3
12 7 16
4 10 11 6
9 5 3 9 4 
输出：
44
*/