Does this problem have overlapping subproblems?

user_16042459 0
Viewed 172

I am trying to solve this question on LeetCode.com:

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).

The solution I am referring is as below:

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 don't follow how this problem is solvable by dynamic programming. The states apparently are the row i and the sum (from row 0 to row i-1). Given that the problem constraints are:

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

My understanding is that we would never encounter a sum that we have previously encountered (all values are positive). Even the debug cout statement that I added does not print anything on the sample inputs given in the problem.

How could dynamic programming be applicable here?

dynamic-programming algorithm c++
1 Answers

This problem is NP-hard, since the 0-1 knapsack problem reduces to it pretty easily.

This problem also has a dynamic programming solution that is similar to the one for 0-1 knapsack:

  1. Find all the sums you can make with a number from the first row (that's just the numbers in the first row):
  2. For each subsequent row, add all the numbers from the ith row to all the previously accessible sums to find the sums you can get after i rows.

If you need to be able to recreate a path through the matrix, then for each sum at each level, remember the preceding one from the previous level.

There are indeed overlapping subproblems, because there will usually be multiple ways to get a lot of the sums, and you only have to remember and continue from one of them.

Here is your example:

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

As you see, we can make the target sum. There are a few ways:

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

Some targets like 15 have a lot more ways. As the size of the matrix increases, the amount of overlap tends to increase, and so this solutions is reasonably efficient in many cases. The total complexity is in O(M * N * max_weight).

But, this is an NP-hard problem, so this is not always tractable -- max_weight can grow exponentially with the size of the problem.

user_54835260
Related