看 OI-wiki 的 DP，有个疑问：
这里为什么“每一步决策都是最优的”。我觉得换其他数字举例，可能会有最优的路径的中间步骤是局部最优的
2 Likes
This is the same as the shortest path in a graph. Suppose that the path 7‑3‑8‑7 from the 7 in row 1 to the 7 in row 4 is not optimal, then it indicates that there is another route from the 7 in row 1 to the 7 in row 4 whose sum of numbers is greater than that of 7‑3‑8‑7. If such a route exists, then 7‑3‑8‑7‑5 is not optimal, which contradicts the assumption.
1 Like
就是动态规划里的最优化原理。
在此例中 第一行到第五行的最优路径 就等于
第一行到第四行的第 i 个数字的最优路径 加 它到左下方或右下方（哪个大去哪）
再对 i=1，2，3，4 的总路径长度取 max。
所以这里的 7-3-8-7 指的不是第一行到第四行的最优路径
而是第一行到第四行的第二个数字也就是 7 的最优路径。
1 Like