HDOJ 2084 数塔【简单DP】

本文主要是介绍HDOJ 2084 数塔【简单DP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目详见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];elsearray[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

这篇关于HDOJ 2084 数塔【简单DP】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---