本文主要是介绍数塔 动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include <iostream>
using namespace std;
#define MAX 20
int main()
{
int i,j,n,a[MAX][MAX];
cout<<"请输入塔的层数："<<endl;
cin>>n;
for(i=0;i<n;++i)
{
cout<<"请输入第"<<i<<"层塔的数据："<<endl;
for(j=0;j<=i;++j)
{
cin>>a[i][j];
}
}
for(i=n-2;i>=0;--i)
{
for(j=0;j<=i;j++)
{
if(a[i][j]+a[i+1][j]>a[i][j]+a[i+1][j+1])
a[i][j]+=a[i+1][j];
else
a[i][j]+=a[i+1][j+1];
}
}
cout<<a[0][0]<<endl;
return 0;
}
在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算。核心是从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。所以实际求解时，可从底层开始，层层递进，最后得到最大值，这就是所谓的自顶向下分析法，自底向上求解法。
#include<iostream>
#include<cstring>
using namespace std;
#define N 4 //四层数塔
int a[N+1][N+1]; //输入数塔
int dp[N+1][N+1]; //每个状态的最优解 即最大值
int shuta(int i,int j)
{
if(dp[i][j]>=0)
return dp[i][j];
else
return dp[i][j]=a[i][j]+(i==N?0:shuta(i+1,j)>shuta(i+1,j+1)?shuta(i+1,j):shuta(i+1,j+1));
}
int main()
{
memset(dp,-1,sizeof(dp));
int i,j;
for(i=0;i<N;++i)
{
for(j=0;j<=i;++j)
{
cin>>a[i][j];
}
}
cout<<shuta(0,0)<<endl;
}
/*
状态转移方程：
dp[i][j]={a[i][j]+max{dp[i+1][j],dp[i+1][j+1]}}
dp[i][j]表示i,j位置的最优解（子问题）
测试数据：
9
12 15
10 6 8
2 18 9 5
结果：49
1
3 2
4 10 1
4 3 2 20
结果：24
*/
这篇关于数塔 动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
