数字三角形

数字三角形

时间限制：2 sec

空间限制：256 MB

问题描述

给定一个高度为 n 的“数字三角形”，其中第 i 行（1<=i<=n）有 i 个数。（例子如下图所示）

初始时，你站在“数字三角形”的顶部，即第一行的唯一一个数上。每次移动，你可以选择移动到当前位置正下方或者当前位置右下方的位置上。即如果你在 (i,j)（表示你在第i 行从左往右数第j 个数上，下同），你可以选择移动到 (i+1,j) 或 (i+1,j+1)。

你想让你经过的所有位置（包括起点和终点）的数字总和最大。求这个最大值。

输入格式

第一行一个正整数 n，表示数字三角形的大小。

第 2 行到第 n+1 行，第 i+1 行为 i 个用空格隔开的非负整数，描述数字三角形的第 i

行。

输格式

一行一个整数，表示经过路径上数的最大总和。

样例输入

4

1

23

45 6

78 9 10

样例输

样例解释

不停地向右下走即可。

数据范围

对于 50% 的数据，保证 n<=5。

对于 100% 的数据，保证 n<=1,000，保证数字三角形内的数不超过 10^6。

提示

[如果我们使用搜索算法，我们会在搜索时记录哪些信息呢？] [当前到达的点的坐标、当前经过路径上数的总和！]

[总和显然是越大越好！]

[于是可以设计出状态：dp[i][j] 表示走到坐标为 (i,j) 的点时的最大总和。] [很容易就可以设计出]

代码

#include <iostream> #include <vector> #include <algorithm>

#pragma warning(disable:4996) using namespace std;

// ================= 代码实现开始 =================

/* 请在这里定义你需要的全局变量 */ vector<vector<int>> dp;

// 本函数计算答案（最大经过位置数字总和）

// n：描述数字三角形大小，意义同题目描述

// a：描述整个数字三角形，第 i 行的第 j 个数存放在 a[i][j]

// 中（你需要特别注意的是，所有下标均从 1 开始，也就是说下标为 0 的位置将存放无效信息）

// 返回值：最大经过位置数字总和

int getAnswer(int n, vector<vector<int>> a) {

/* 请在这里设计你的算法 */

dp.resize(n + 1);

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

{

dp[i].resize(i + 2);

a[i][i + 1] = 0;

a[i][0] = 0;

}

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

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

{

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

dp[i][j] = dp[i][j];

}

int ans = 0;

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

ans = max(ans, dp[n][i]);

return ans;

}

// ================= 代码实现结束 =================

int main() {

int n;

vector<vector<int>> a;

scanf("%d", &n);

a.resize(n + 1);

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

a[i].resize(i + 2);

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

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

scanf("%d", &a[i][j]);

int ans = getAnswer(n, a);

printf("%d\n", ans);

return 0;

}