带障碍物的最小路径和
在各个单元格间传递最优代价
带障碍物的最小路径和 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
从计数到计费
现在每个单元格都有一个数值，而您希望找到到达右下角的最低成本。目标从计算路径数量转变为最小化成本。
定义状态
令 dp[i][j] 表示到达单元格 (i, j) 的最小总成本。网格相同，移动方式相同，但这次跟踪的是总和而不是计数。
状态转移
您需要选择两个进入方向的相邻单元格中成本较低的一个，然后加上当前单元格的值。这个最小值选择是递推关系的核心。
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])标记障碍物
障碍物是您无法站立的单元格。将它的成本设为无穷大，这样任何经过它的路径都不会成为最小值。
INF = float('inf')简洁地阻断它
当网格标记某个单元格为阻塞时，只需将它的 dp 设为无穷大，然后继续处理。取最小值的步骤会自然地避开它。
if blocked(i, j):
dp[i][j] = INF
continue保护起点
如果起始单元格本身被阻塞，那么根本不存在路径。请首先检查这一点，以免返回无意义的成本。
初始化第一个单元格
起点没有可以到达它的相邻单元格，因此它的成本就是自身的值。请在循环开始前设置 dp[0][0]。
dp[0][0] = grid[0][0]处理边界
顶行只能从左侧转移，最左列只能从上方转移。请处理好这些边界，这样就不会读取网格之外的内容。
无穷大会传播
加上无穷大仍然是无穷大，因此完全被阻断的单元格会保留其 INF 成本。无法到达的单元格会自动表明自身的状态。
读取结果
最小成本位于右下角的单元格中。如果该值仍然是无穷大，那么根本不存在有效路径。
ans = dp[m-1][n-1]
if ans == INF:
ans = -1贪心为何在这里失效
始终走向较小的相邻单元格可能会让您陷入困境。只有完整的 DP 才能保证找到全局成本最低的路径，而不是只看眼前的贪心选择。
快速检查
怎样让路径 DP 避开被阻塞的单元格，而不必为每个相邻单元格编写特殊处理？
回顾：带障碍物的最短路径
选择成本较低的相邻单元格并加上当前单元格的值，将被阻塞的单元格设为无穷大，然后读取右下角。如果那里是 INF，就表示不存在路径。🧱
常见问题解答
「带障碍物的最小路径和」课时是免费的吗？
是的 — 「带障碍物的最小路径和」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「带障碍物的最小路径和」这节课中我会学到什么？
在各个单元格间传递最优代价 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「带障碍物的最小路径和」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。