Problem Description
给你一个大小为 m x n 的整数矩阵 mat 和一个整数 target 。
从矩阵的 每一行 中选择一个整数，你的目标是 最小化 所有选中元素之 和 与目标值 target 的 绝对差 。
返回 最小的绝对差 。
a 和 b 两数字的 绝对差 是 a - b 的绝对值。
note
m == mat.lengthn == mat[i].length1 <= m, n <= 701 <= mat[i][j] <= 701 <= target <= 800
e.g.
示例 1：
1
2
3
4
5
6
7
| 输入：mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
输出：0
解释：一种可能的最优选择方案是：
- 第一行选出 1
- 第二行选出 5
- 第三行选出 7
所选元素的和是 13 ，等于目标值，所以绝对差是 0 。
|
示例 2：
1
2
3
4
5
6
7
| 输入：mat = [[1],[2],[3]], target = 100
输出：94
解释：唯一一种选择方案是：
- 第一行选出 1
- 第二行选出 2
- 第三行选出 3
所选元素的和是 6 ，绝对差是 94 。
|
示例 3：
1
2
3
4
| 输入：mat = [[1,2,9,8,7]], target = 6
输出：1
解释：最优的选择方案是选出第一行的 7 。
绝对差是 1 。
|
Solution
第 255 场周赛第三题，一开始就看出来是 dp 了，不过一下子妹写出来，最后还是靠的记忆化递归过的。
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
| public class Solution {
Map<Integer, Set<Integer>> map;
int ans = 0x3f3f3f3f;
public int minimizeTheDifference(int[][] mat, int target) {
map = new HashMap<>();
for (int[] ints : mat) {
Arrays.sort(ints);
}
dfs(mat, target, 0, 0);
return ans;
}
public void dfs(int[][] mat, int target, int curr, int step) {
if (step >= mat.length) {
ans = Math.min(Math.abs(target - curr), ans);
return;
}
for (int i = 0; i < mat[0].length; i++) {
if (curr + mat[step][i] - target > ans) {
break;
}
if (map.get(step) != null && map.get(step).contains(curr + mat[step][i])) {
continue;
}
map.put(step, map.getOrDefault(step, new HashSet<>()));
map.get(step).add(curr + mat[step][i]);
dfs(mat, target, curr + mat[step][i], step + 1);
}
}
}
|