2297. 松鼠“跳跳”的松果金字塔大冒险
1000ms
256MB
简单
递推算法
题目描述
松鼠“跳跳”在坚果金字塔中进行冒险。金字塔共有 $N$ 层，第 $i$ 层有 $i$ 个房间。
跳跳从金字塔最顶端的房间出发，每次它只能选择移动到当前房间**左下方**或**右下方**相邻的房间，直到到达金字塔的底部。
每个房间内都有一定数量的松果，请你计算跳跳在冒险过程中能够收集到的松果的最大总数。
输入格式
- 第一行包含一个正整数 $N$ ($1 \le N \le 1000$)，表示金字塔的行数。
- 接下来 $N$ 行，第 $i$ 行包含 $i$ 个非负整数（每个整数 $\le 100$），代表该层每个房间内的松果数量。
输出格式
- 输出一行一个整数，表示路径上数字之和的最大值。
样例 1
输入 (Input)
5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11
输出 (Output)
86
样例说明
- 对于所有数据：$1 \le N \le 1000$。
- 房间内松果数 $V$ 满足 $0 \le V \le 100$。
- **样例解释**：
最大路径为 $13 o 8 o 26 o 15 o 24$，最大松果总数为：$13 + 8 + 26 + 15 + 24 = 86$。
- **算法提示**：可以使用动态规划（DP）**自底向上**进行递推。
设 $dp[i][j]$ 表示从第 $i$ 行第 $j$ 列出发到达底部的最大和，则状态转移方程为：
$$dp[i][j] = val[i][j] + \max(dp[i+1][j], dp[i+1][j+1])$$
自底向上计算可以有效避免复杂的边界判断，且可以使用一维滚动数组将空间复杂度优化至 $O(N)$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功