动态规划 · 分步推演

最小路径和:一步步看 dp[j] 是怎么算出来的

矩阵 [[1,3,1],[1,5,1],[4,2,1]],配合一维数组 dp[j] = min(dp[j-1], dp[j]) + grid[i][j] 逐格推演。 重点看右侧"dp 一维带"——同一个格子在被覆盖前后,代表的是网格里两个不同的位置。

网格(每格永久记录自己算出的值)
左边来源 上边来源 当前计算格
dp 一维带(旧值会被覆盖)
带里的每一格会被反复覆盖——覆盖前代表"上边",覆盖后代表"当前行"。
尚未开始
点击「下一步」开始推演
我们要计算从左上角 (0,0) 到右下角 (2,2) 的最小路径和。 每一步都会显示当前在算哪个格子,以及它是从左边还是上边推过来的。
步骤 0 / 9
推演记录
☕ 如果这篇文章帮到你,可以请作者喝杯咖啡 · 爱发电