HDU 2084 数塔（动态规划DP）

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=2084

题目分析：此题采用动态规划自底向上计算，如果我们要知道所走之和最大，那么最后一步肯定是走最后一排数其中一个，向上退，倒数第二步肯定走最后一排数对应的倒数第二排最大的一个（将最后对应最后步走的最大的数加起来存在倒数第二步的数组中）再向上推，一直推到最上面的第0步，那么 $dp[0][0]$ ]最后所存的结果一定是最大的。

代码如下：

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 100;

int data[N][N];

int dp[N][N];

int n, t;

void tower_walk()

{

    for (int i = 0; i < n; ++i)

        dp[n - 1][i] = data[n - 1][i];

    int temp_max;

    for (int i = n - 1; i >= 0; --i)

        for (int j = 0; j <= i; ++j) {

            temp_max = max(dp[i + 1][j], dp[i + 1][j + 1]);

            dp[i][j] = temp_max + data[i][j];

        }

}

int main()

{

	cin >> t;

	while (t--) {

		cin >> n;

		for (int i = 0; i < n; i++)

			for (int j = 0; j <= i; j++)

				cin >> data[i][j];

		tower_walk();

		cout << dp[0][0] << endl;

	}

	return 0;

}

巴特西

HDU 2084 数塔（动态规划DP）

最新文章

热门文章

巴特西

HDU 2084 数塔 （动态规划DP）

最新文章

热门文章

HDU 2084 数塔（动态规划DP）