【初学动态规划】之数塔

这两天初学动态规划，看了几个简单的DP案例，很是头大，于是想先做一个小小的总结。

作为入门，师兄推荐数塔这题，让我了解DP的思想。

所谓数塔，又称数字三角形，就是给出一个数字塔阵，求从塔顶到塔底连接的最大值。

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

这道题很容易理解，求解的路径也十分清晰：

#include <iostream>//数字三角形/数塔
using namespace std;

int m[101][101];//保存输入的数塔
int ans[101][101];//保存i行j列的状态（即最大值）

inline int max(int a,int b)  {return a>b?a :b;}

int main()
{
	int n,cas;
	cin>>cas;//输入层数
	while(cas--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=i;j++)
				cin>>m[i][j];
		for(int i=1;i<=n;i++) ans[n][i]=m[n][i];//设置最底层的初始状态
		
		for(int i=n-1;i>=1;i--)//从最底层开始，向上求解
			for(int j=1;j<=i;j++)//从最底层的第一个开始计算
				ans[i][j]=m[i][j]+max( ans[i+1][j],ans[i+1][j+1] );//每上一层的状态由下一层的两种可能的更大值生成
		cout<<ans[1][1]<<endl;//由于自底向上,所以最上面那个的状态即是最优解
	}
	return 0; 
}