题目描述
给你一个大小为 m x n 的整数矩阵 mat 和一个整数 target 。 从矩阵的 每一行 中选择一个整数，你的目标是 最小化 所有选中元素之 和 与目标值 target 的 绝对差 。 返回 最小的绝对差 。 a 和 b 两数字的 绝对差 是 a - b 的绝对值。
Example 1:
输入：mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13 输出：0 解释：一种可能的最优选择方案是：
- 第一行选出 1
- 第二行选出 5
- 第三行选出 7 所选元素的和是 13 ，等于目标值，所以绝对差是 0 。
Example 2:
输入：mat = [[1],[2],[3]], target = 100 输出：94 解释：唯一一种选择方案是：
- 第一行选出 1
- 第二行选出 2
- 第三行选出 3 所选元素的和是 6 ，绝对差是 94 。
Example 3:
输入：mat = [[1,2,9,8,7]], target = 6 输出：1 解释：最优的选择方案是选出第一行的 7 。 绝对差是 1 。
Constraints:
- m == mat.length
- n == mat[i].length
- 1 <= m, n <= 70
- 1 <= mat[i][j] <= 70
- 1 <= target <= 800
解题思路
- 用暴搜会超时
- 参考题解。
C++代码
class Solution {
public:
bool dp[80][4900];
int minimizeTheDifference(vector<vector<int>>& mat, int target) {
int MAX = 4900;
int row = mat.size();
int col = mat[0].size();
for(auto& i : mat[0]){
dp[0][i] = true;
}
for(int i = 1; i < row; i++){
for(int j = 0; j < col; j++){
int num = mat[i][j];
for(int k = num; k < MAX; k++){
if(dp[i - 1][k - num]){
dp[i][k] = true;
}
}
}
}
int res = INT_MAX;
for(int i = 0; i < MAX; i++){
if(dp[row - 1][i]){
res = min(res, abs(i - target));
}
}
return res;
}
};
