文章目錄

• • 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; // 可以拿 標記為1for(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;} };

1732 ms 68.5 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1981. 最小化目标值与所选元素的差（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。