LeetCode 1981. 最小化目标值与所选元素的差（DP）

Michael阿明

发布于 2021-09-06 03:57:45

54300

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

文章目录

- 1. 题目
- 2. 解题

1. 题目

给你一个大小为 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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/minimize-the-difference-between-target-and-chosen-elements 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int m = mat.size(), n = mat[0].size(), diff = INT_MAX, limit = 4901;
        vector<int> dp(limit, 0);
        for(int i = 0; i < n; ++i)
            dp[mat[0][i]] = 1; // 可以拿 标记为1
        for(int i = 1; i < m; ++i)
        {
            vector<int> temp(limit, 0);
            for(int v = limit-1; v >= 0; --v)
            {
                if(dp[v] == 0) // 前面状态不存在
                    continue;
                for(int j = 0; j < n; ++j)
                {
                    if(v+mat[i][j] < limit)
                        temp[v+mat[i][j]] = 1;
                }
            }
            swap(temp, dp);
        }
        for(int i = 0; i < limit; ++i)
        {
            if(dp[i])
            {
                diff = min(diff, abs(i-target));
            }
        }
        return diff;
    }
};