学步园

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

题目的意思就是从上到下，找到一个路径加起来和是最大的。
这个很简单，就是一个表达式的事，没什么可多想的。遍历是不现实的，也没必要。这个DP 很好想，是我做过最简单的DP了。
状态转移方程
	array[i][j]+=MAX{array[i-1][j-1]，array[i-1][j]}
不多说了，直接上代码

#include <iostream>   
using namespace std;    

int main()
{	
	int array[101][101];
	int i,j;
	int C,N,Max;
	for(i=0;i<=100;i++)
	{
		for(j=0;j<=100;j++)
			array[i][j]=0;
	}
	cin>>C;
	while(C--)
	{
		cin>>N;
		for(i=1;i<=N;i++)
		{
			for(j=1;j<=i;j++)
				cin>>array[i][j];
		}
		for(i=1;i<=N;i++)
		{
			for(j=1;j<=i;j++)
			{
				if(array[i-1][j-1]>=array[i-1][j])
					array[i][j]+=array[i-1][j-1];
				else
					array[i][j]+=array[i-1][j];
			}
		}
		Max=0;
		for(i=1;i<=N;i++)
			if(array[N][i]>Max)
				Max=array[N][i];
		cout<<Max<<endl;
	}
	return 0;
}

转载请注明出处http://blog.csdn.net/liangbopirates/article/details/9709071