仅可向右/向下移动时，二维网格最低成本路径算法疑问

你的方法是动态规划，不是贪心 #

你构建DP网格计算每个单元格dp[i][j]的逻辑，是标准的动态规划解法：dp[i][j]代表从起点到(i,j)的最低成本，由左侧或上方单元格的最小成本加上当前单元格值得到。这和贪心算法完全不同——贪心是每一步只选当下局部最优，不考虑全局后续影响，而你的DP是基于全局最优的子问题结果推导，具备无后效性，能保证全局最优。

路径错误的核心原因 #

总成本正确但路径错误，问题出在路径回溯环节：

• 正确的回溯逻辑应该从终点倒推：从右下角(m-1,n-1)出发，比较上方单元格(m-2,n-1)的dp值与左侧单元格(m-1,n-2)的dp值，选择数值较小的那个方向（因为dp[i][j]是起点到该点的最低成本，数值小意味着这条路径是到达当前单元格的最优路径）。
• 如果你回溯时错误地比较了当前单元格到下一个单元格的直接成本，而非依赖已计算的dp值，就会导致路径偏差。

该方法的正确性验证 #

在仅允许向右/向下移动的约束下，这个DP方法是完全正确的。因为每个单元格的最优解仅依赖左侧和上方的子问题最优解，不存在后续决策影响之前结果的情况，完全满足动态规划的适用条件，能同时得到正确的总成本和路径。

关于参考答案的疑问 #

如果你的DP计算和回溯逻辑都正确，那么大概率是参考答案有误。仅向右/向下移动的网格最低成本路径问题，标准解法就是这类二维动态规划，不存在时间复杂度更优的解法（当前方法时间复杂度为O(m*n)，空间上可优化为O(n)或O(m)，但核心逻辑一致）。

空间优化的变种实现 #

若要优化空间占用，可使用一维DP数组替代二维网格：

• 初始化一维数组dp，长度等于网格列数，dp[0]设为起点值，第一行依次累加右侧单元格值；
• 处理后续每一行时，先更新dp[0]为上一行dp[0]加当前单元格值，再从左到右遍历，更新dp[j] = min(dp[j-1], dp[j]) + grid[i][j]；
• 最终dp[n-1]即为最低总成本，路径回溯需额外记录或重新推导。

内容的提问来源于stack exchange，提问作者Łukasz