🐰😺🔺 兔猫信奥学院·加菲老师的三角探秘之旅 🔺😺🐰

在信奥学院的秘法塔中，有一块呈三角形排列的能量水晶阵列。加菲老师对小兔和小猫说：“从阵列顶端的水晶开始，每一步只能向下一行的左邻或右邻移动，即如果当前在第 $i$ 行下标 $j$，下一步可以到第 $i+1$ 行的下标 $j$ 或 $j+1$。每颗水晶都有自己的能量消耗值，我们要沿途收集水晶能量，并使总消耗最小。你们能找到从顶端到底部的最小路径和吗？”

输入格式

第一行：整数 r，表示三角形的行数。
接下来 r 行，第 i 行包含 i 个整数 triangle[i-1][0…i-1]，用空格分隔，表示水晶的能量消耗（可能为负数）。

• $1 \le r \le 200$
• $-10^4 \le triangle[i][j] \le 10^4$
• 且 triangle[i].length = i+1，triangle[0].length = 1

输出格式

输出一个整数，表示自顶向下的最小路径和。

样例 1

4
2
3 4
6 5 7
4 1 8 3

11

• 解释：
  最优路径为 $2\to3\to5\to1$，路径和$$2+3+5+1=11.$$

样例 2

1
-10

-10

• 解释：
  只有一行水晶，直接取 $-10$。

🎓 加菲老师寄语：
通过此题，同学们可以体会到如何在 $O(r)$ 空间内完成三角形最小路径和的动态规划。熟练后，你就能应对更多维度和约束的路径优化问题，加油攀登更高学术峰巅！