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

Question

我正在解决一些关于LeetCode的问题。其中一个问题是：

给定一个由非负数填充的mxn网格，找到一条从左上到右下的路径，该路径使沿其路径的所有数字之和最小化。你只能在任何时间点向下或向右移动。

社论以及发布的解决方案都使用动态规划。投票最多的解决方案之一如下：

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,2500]
[100500500]
[1,3,4]
]

我的怀疑是因为在DP中，子问题的解决方案是全局解决方案（最优子结构）的一部分。然而，正如上面所看到的，当我们在（2,100）中选择2的局部选择时，我们可能是错误的，因为未来的路径可能太昂贵了（围绕2的所有数字都是500s）。那么，在这种情况下如何使用动态编程是合理的呢？

总结一下：

1. 我们不应该使用回溯吗，因为如果我们之前做出了错误的选择（查看局部最大值），我们可能不得不收回我们的路径？
2. 这怎么是一个动态编程问题？

注：上述解决方案肯定会运行。

Answer 1

谢谢你的意见

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

求和数组结果

[
[  1,   3,  503]
[101, 503, 1003]
[102, 105,  109]
]

我们甚至可以追溯最短路径：

109, 105, 102, 101, 1

算法不检查每条路径，而是使用它可以采用先前最佳路径的属性来计算当前成本：

sum[i][j] = min(sum[i - 1][j], // take better path between previous horizontal
                sum[i][j - 1]) // or previous vertical
            + grid[i][j]; // current cost

Answer 2

如果我们之前做出了错误的选择（查看局部最大值），我们是否应该使用回溯，因为我们可能不得不收回我们的路径？

在现实世界的场景中，有相当多的因素将决定哪种算法更适合解决这个问题。

这种DP解决方案可以在处理最坏情况时为您提供最佳性能/内存使用率。

任何回溯/dijkstra/A*算法都需要维护完整的矩阵和开放节点列表。这个DP解决方案只是假设每个节点最终都会被访问，所以它可以放弃开放节点列表，只需维护成本缓冲区。

通过假设每个节点都将被访问，它还消除了算法中的“下一步打开哪个节点”部分。

所以，如果我们所追求的是最佳最坏情况下的性能，那么这个算法实际上将很难被击败。但这是不是我们想要的是另一回事。

这是一个动态规划问题吗？

这只是一个动态规划问题，因为它存在一个动态规划解决方案。但DP绝不是解决这一问题的唯一方法。

编辑：在我被扣篮之前，是的，有更节省内存的解决方案，但在最坏的情况下，CPU成本非常高。

Answer 3

上面的例子表明，贪婪的问题解决方案不一定会产生最优解，这一点你是绝对正确的。

然而，这个问题的DP解决方案并不完全使用这种策略。DP解决方案背后的想法是，为每个位置计算以该位置为终点的最短路径的成本。在解决整体问题的过程中，DP算法最终将计算通过网格中2的一些最短路径的长度，但在确定返回的整体最短路径时，它不一定使用这些中间最短路径。试着在你的例子中追踪上面的代码——你看到它是如何计算的，然后不使用其他路径选项吗？