这个问题有重叠的子问题吗？

Question

我正在尝试在 LeetCode.com 上解决 this question:

You are given an m x n integer matrix mat and an integer target. Choose one integer from each row in the matrix such that the absolute difference between target and the sum of the chosen elements is minimized. Return the minimum absolute difference. (The absolute difference between two numbers a and b is the absolute value of a - b.)
So for input mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13, the output should be 0 (since 1+5+7=13).

我referring的解决方案如下：

int dp[71][70 * 70 + 1] = {[0 ... 70][0 ... 70 * 70] = INT_MAX};
int dfs(vector<set<int>>& m, int i, int sum, int target) {
    if (i >= m.size())
        return abs(sum - target);
    if (dp[i][sum] == INT_MAX) {
        for (auto it = begin(m[i]); it != end(m[i]); ++it) {
            dp[i][sum] = min(dp[i][sum], dfs(m, i + 1, sum + *it, target));
            if (dp[i][sum] == 0 || sum + *it > target)
                break;
        }
    } else {
        // cout<<"Encountered a previous value!\n";
    }

    return dp[i][sum];
}
int minimizeTheDifference(vector<vector<int>>& mat, int target) {
    vector<set<int>> m;
    for (auto &row : mat)
        m.push_back(set<int>(begin(row), end(row)));
    return dfs(m, 0, 0, target);
}

我不明白这个问题是如何通过动态规划解决的。这些状态显然是 i 行和 sum 行（从 0 行到 i-1 行）。鉴于问题约束是：

m == mat.length
n == mat[i].length
1 <= m, n <= 70
1 <= mat[i][j] <= 70
1 <= target <= 800

我的理解是，我们永远不会遇到我们以前遇到过的 sum（所有值为正）。即使是我添加的调试 cout 语句也不会在问题中给出的样本输入上打印任何内容。

动态规划如何适用于此？

Answer 1

这个问题是 NP-hard 问题，因为 0-1 背包问题很容易归结为它。

这道题也有类似0-1背包的动态规划解法：

找出第一行中的数字（即第一行中的数字）可以得出的所有总和：
对于每个后续行，将第 i 行的所有数字添加到所有先前可访问的总和，以找到在 i 行后可以获得的总和。

如果您需要能够重新创建通过矩阵的路径，那么对于每个级别的每个总和，请记住上一级的前一个。

确实存在重叠的子问题，因为通常会有多种方法可以得到很多和，你只需要记住其中一种并继续。

这是你的例子：

sums from    row 1:  1, 2, 3
sums from rows 1-2:  5, 6, 7, 8, 9
sums from rows 1-3:  12, 13, 14, 15, 16, 17, 18

如您所见，我们可以得出目标总和。有几种方法：

7+4+2, 7+5+1, 8+4+1

像 15 这样的一些目标有更多的方法。随着矩阵大小的增加，重叠量趋于增加，因此该解决方案在许多情况下相当有效。总复杂度为 O(M * N * max_weight).

但是，这个是一个 NP-hard 问题，所以这并不总是易于处理的 -- max_weight 可以随着问题的大小呈指数增长。

这个问题有重叠的子问题吗？

Does this problem have overlapping subproblems?

c++

algorithm

dynamic-programming