📌 📄 内容摘要:
Karlre (@Karlbaey) 在 半夜了，想玩动态规划了 中发帖
想学动态规划了，然后就找了这题当作入门。
LG_P1216_[IOI_1994_/_USACO1.5]_数字三角形_Number_Triangles
然后知道动态规划的主要思路就是递推。但是在这之前还要先寻找状态，并且写出状态转移方程。
原题中的输入是这样的。
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
然后读题，先推一推。
因为对于第 n 行（n >= 2），得到的结果只能从第 n-1 行来。所以对于到第 n 行和最大的一条路径，走到第 n-1 行时得到的和也一定是最大值。
这一句比较拗口，其实拿原题中的画就很好解释了。
[Triangle]
（最大路径：7 -> 3 -> 8 -> 7 -> 5）
用二维数组 triangle 表示上图的三角形，记 dp[i][j] 为走到 triangle[i][j] 能获得的最大值[1]。
用上面的结论，...
────────── 链接信息 ──────────
🔗 论坛链接: linux.do
📎 访问地址: https://linux.do/t/topic/1613700/1
─────────────────────────────
📢 来源：LINUX DO
