最小化目标值与所选元素的差

5852. 最小化目标值与所选元素的差

难度中等3收藏分享切换为英文接收动态反馈

给你一个大小为 m x n 的整数矩阵 mat 和一个整数 target 。

从矩阵的 每一行 中选择一个整数，你的目标是 最小化 所有选中元素之 和 与目标值 target 的 绝对差 。

返回 最小的绝对差 。

a 和 b 两数字的 绝对差 是 a - b 的绝对值。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
输出：0
解释：一种可能的最优选择方案是：
- 第一行选出 1
- 第二行选出 5
- 第三行选出 7
所选元素的和是 13 ，等于目标值，所以绝对差是 0 。

示例 2：

输入：mat = [[1],[2],[3]], target = 100
输出：94
解释：唯一一种选择方案是：
- 第一行选出 1
- 第二行选出 2
- 第三行选出 3
所选元素的和是 6 ，绝对差是 94 。

示例 3：

输入：mat = [[1,2,9,8,7]], target = 6
输出：1
解释：最优的选择方案是选出第一行的 7 。
绝对差是 1 。

提示：

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

通过次数1,500

提交次数7,936

递归(超时)

  
 public int minimizeTheDifference(int[][] mat, int target) {
       this.target = target;
       dfs(mat, 0, target);
       return min;
   }

public void dfs(int[][] mat, int row, int res) {
       if (row == mat.length) {
           min = Math.min(min, Math.abs(res));
           return;
       }
       for (int j = 0; j < mat[0].length; j++) {
           dfs(mat, row + 1, res - mat[row][j]);
       }
   }

记忆化搜索（超时）

   public int minimizeTheDifference(int[][] mat, int target) {
       this.target = target;
       dfs(mat, 0, target);
       return min;
   }
   int min = Integer.MAX_VALUE;
   int target = 0;
   Map<String, Integer> map = new HashMap<>();

public int dfs(int[][] mat, int row, int sum) {
       String key = row + "|" + sum;
       if (map.containsKey(key)) return map.get(key);

       if (row == mat.length) {
           min = Math.min(min, Math.abs(sum - target));
           return min;
       }
       int temp = Integer.MAX_VALUE;

       for (int j = 0; j < mat[0].length; j++) {
           temp = Math.min(dfs(mat, row + 1, sum + mat[row][j]), temp);
       }

       map.put(key, temp);
       return temp;
   }

动态规划

数组的范围是70，每个数字的最大值是70，可选的和最大为70*70=4900

对于每一行，如果某个和可以通过上一行的某个和加当前行的某个数字得到，那么当前的和是可达的。

计算完成后，最后一行的和如果可达，那么计算target与可达和的差的绝对值，取最小。

public int minimizeTheDifference(int[][] mat, int target) {
    int n = mat.length;
    int m = mat[0].length;
    int MAX = 70 * 70 + 1;
    int[][] dp = new int[n + 1][MAX];

    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int k = 0; k < MAX; k++) {
            for (int j = 1; j <= m; j++) {
                if (k >= mat[i - 1][j - 1] && dp[i - 1][k - mat[i - 1][j - 1]] == 1) {
                    dp[i][k] = 1;
                }
            }
        }
    }

    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < MAX; i++) {
        if (dp[n][i] > 0) {
            ans = Math.min(ans, Math.abs(target - i));
        }
    }
    return ans;
}

赏

谢谢你请我吃糖果

微信