7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(图一)
图一表示一个5行的数字三角形。假设给定一个n行数字三角形,计算出从三角形顶至底的一条路径，使该路径经过的数字总和最大。
每一步只能由当前位置向下或向右下。
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $1735$ | 正确数量 | $1100$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 | 动态规划 二维数组 递推 递归 |
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(图一)
图一表示一个5行的数字三角形。假设给定一个n行数字三角形,计算出从三角形顶至底的一条路径，使该路径经过的数字总和最大。
每一步只能由当前位置向下或向右下。
你的程序要能接受标准输入。第一行包含一个整数T，表示总的测试次数。
对于每一种情况：第一行包含一个整数N,其中1 < N < 100,表示三角形的行数。
接下来的N行输入表示三角形的每一行的元素Ai,j，其中0 < Ai,j < 100。
输出每次测试的最大值并且占一行。
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
30
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$0 $ms] | 开门 | 1059870 | 2024-01-12 10:32:02 |
| 内存最少[$0 $KB] | yaoking | 615047 | 2020-10-07 20:51:14 |
| 第一AC | 范晋豪@信息与计算科学142 | 4201 | 2016-05-26 16:06:33 |
| 第一挑战 | 范晋豪@信息与计算科学142 | 4201 | 2016-05-26 16:06:33 |
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|---|---|---|
| 1800 | 2023-2024-2学期<计算机专业竞赛实训> 第4周练习：递推和动态规划【22计算机】 | 2024-03-18 00:00:00 | 请登录 |
| 1788 | 2023-2024-1学期《程序设计技能实训》递推和动态规划【23计算机】 | 2023-12-18 00:00:00 | 请登录 |
| 1740 | 2022-2023-2学期<计算机专业竞赛实训> 第6周练习：递推和动态规划【21计算机12345】 | 2023-03-27 00:00:00 | 请登录 |
| 1733 | 2022-2023-1学期《程序设计技能实训》动态规划【22计算机】 | 2022-12-28 00:00:00 | 请登录 |
| 1685 | 2021-2022-2学期<算法分析与设计> 第6周练习：递推和动态规划 | 2022-03-28 00:00:00 | 请登录 |