c++ - 这不应该使用回溯算法吗？

Question

我正在解决 LeetCode 上的一些问题。其中一个问题是:

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.You can only move either down or right at any point in time.

社论以及发布的解决方案均使用动态规划。最受欢迎的解决方案之一如下:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size(); 
        vector<vector<int> > sum(m, vector<int>(n, grid[0][0]));
        for (int i = 1; i < m; i++)
            sum[i][0] = sum[i - 1][0] + grid[i][0];
        for (int j = 1; j < n; j++)
            sum[0][j] = sum[0][j - 1] + grid[0][j];
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                sum[i][j]  = min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
        return sum[m - 1][n - 1];
    }
};

我的问题很简单:这不应该使用回溯来解决吗？假设输入矩阵是这样的:

[
[1,2,500]
[100,500,500]
[1,3,4]
]

我的怀疑是因为在 DP 中，子问题的解决方案是全局解决方案(最优子结构)的一部分。然而，正如上面所见，当我们从 (2,100) 中选择 2 时，我们可能是错误的，因为 future 的路径可能过于昂贵(所有 2 周围的数字都是 500)。那么，在这种情况下如何证明使用动态规划是合理的？

总结:

1. 我们不应该使用回溯，因为如果我们之前做出了错误的选择(查看局部最大值)，我们可能不得不收回我们的路径？
2. 这是一道动态规划题吗？

P.S.:上面的解决方案绝对可以运行。

Answer 1

您在上面说明的示例表明，问题的贪婪解决方案不一定会产生最佳解决方案，您在这一点上是绝对正确的。

然而，这个问题的 DP 解决方案并没有完全使用这个策略。 DP 解决方案背后的想法是为每个位置计算终止于该位置的最短路径的成本。在解决整体问题的过程中，DP 算法最终会计算通过你的网格中的 2 的一些最短路径的长度，但它不一定使用那些中间最短路径时确定返回的总最短路径。尝试在您的示例中跟踪上述代码 - 您是否看到它是如何计算的，然后最终没有使用其他路径选项？