Skip to content

1981. Minimize the Difference Between Target and Chosen Elements 👍

  • Time: $O(m \cdot 70^2)$
  • Space: $O(m \cdot 70^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
 public:
  int minimizeTheDifference(vector<vector<int>>& mat, int target) {
    const int minSum = getMinSum(mat);
    if (minSum >= target)  // No need to consider any larger combination.
      return minSum - target;

    const int maxSum = getMaxSum(mat);
    dp.resize(mat.size(), vector<int>(maxSum + 1, -1));
    return minimizeTheDifference(mat, 0, 0, target);
  }

 private:
  vector<vector<int>> dp;

  int minimizeTheDifference(const vector<vector<int>>& mat, int i, int sum,
                            int target) {
    if (i == mat.size())
      return abs(sum - target);
    if (dp[i][sum] != -1)
      return dp[i][sum];
    int ans = INT_MAX;
    for (const int num : mat[i])
      ans = min(ans, minimizeTheDifference(mat, i + 1, sum + num, target));
    return dp[i][sum] = ans;
  }

  int getMinSum(const vector<vector<int>>& mat) {
    return accumulate(mat.begin(), mat.end(), 0,
                      [](int subtotal, const vector<int>& row) {
      return subtotal + *min_element(row.begin(), row.end());
    });
  }

  int getMaxSum(const vector<vector<int>>& mat) {
    return accumulate(mat.begin(), mat.end(), 0,
                      [](int subtotal, const vector<int>& row) {
      return subtotal + *max_element(row.begin(), row.end());
    });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int minimizeTheDifference(int[][] mat, int target) {
    final int minSum =
        Arrays.stream(mat).mapToInt(row -> Arrays.stream(row).min().getAsInt()).sum();
    if (minSum >= target) // No need to consider any larger combination.
      return minSum - target;

    final int maxSum =
        Arrays.stream(mat).mapToInt(row -> Arrays.stream(row).max().getAsInt()).sum();
    dp = new Integer[mat.length][maxSum + 1];
    return minimizeTheDifference(mat, 0, 0, target);
  }

  private Integer[][] dp;

  private int minimizeTheDifference(int[][] mat, int i, int sum, int target) {
    if (i == mat.length)
      return Math.abs(sum - target);
    if (dp[i][sum] != null)
      return dp[i][sum];
    int ans = Integer.MAX_VALUE;
    for (final int num : mat[i])
      ans = Math.min(ans, minimizeTheDifference(mat, i + 1, sum + num, target));
    return dp[i][sum] = ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
    minSum = sum(min(row) for row in mat)
    if minSum >= target:  # No need to consider any larger combination.
      return minSum - target

    @functools.lru_cache(None)
    def dp(i: int, summ: int) -> int:
      if i == len(mat):
        return abs(summ - target)
      return min(dp(i + 1, summ + num) for num in mat[i])

    return dp(0, 0)