动态规划 专题

HDU 2084 数塔

题目描述

输入输出样例

时空限制

  • Time Limit: 1000/1000 MS (Java/Others)
  • Memory Limit: 32768/32768 K (Java/Others)

思路

简单的动态规划问题。找到递推式即可。

它是从倒数第二行往上开始递推的，每个数都等于它自己加上 正下方 和 斜右方 两者取最大值。

dp[j-1][k-1] += max(dp[j][k], dp[j][k-1]);

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
int dp[110][110];

int main(){
	int n;
	scanf("%d", &n);
	memset(dp,0,sizeof(dp));
	for(int i = 1; i <= n; ++i){
		int m;
		scanf("%d", &m);
		for(int j = 1; j <= m; ++j){
			for(int k = 1; k <= j; ++k){
				scanf("%d",&dp[j][k]);	
			}	
		}
		for(int j = m; j > 1; --j){
			for(int k = m; k > 1; --k){
				dp[j-1][k-1] += max(dp[j][k], dp[j][k-1]);
			}
		}
		printf("%d\n", dp[1][1]);
	}
	return 0;
}