看 OI-wiki 的 DP，有个疑问：
这里为什么“每一步决策都是最优的”。我觉得换其他数字举例，可能会有最优的路径的中间步骤是局部最优的
2 Likes
这个和 graph 中的最短路径一样。假如说从第 1 行的 7 到第 4 行的 7 的 7-3-8-7 不是最优路径，就说明从第 1 行的 7 到第 4 行的 7 有另一条路，其数字加起来是比 7-3-8-7 更大的。如果存在这条路，那么说明 7-3-8-7-5 就不是最优的，与假设前提矛盾。
1 Like
就是动态规划里的最优化原理。
在此例中 第一行到第五行的最优路径 就等于
第一行到第四行的第 i 个数字的最优路径 加 它到左下方或右下方（哪个大去哪）
再对 i=1，2，3，4 的总路径长度取 max。
所以这里的 7-3-8-7 指的不是第一行到第四行的最优路径
而是第一行到第四行的第二个数字也就是 7 的最优路径。
1 Like