本文涉及知识点
C++动态规划
C++背包问题
LeetCode1981. 最小化目标值与所选元素的差
给你一个大小为 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
动态规划 分组背包
动态规划的状态表示
dp1[i][m] 表示前i行是否存在和为m的方案。m ∈ \in ∈[0,target-1]$ dp2[i] 表示是否存在和>=target,如果存在取最小值。不存在则为10000。由于网格(矩阵)全部为正整数,故只会越来越大。空间复杂度:O(mtarget)
动态规划的状态表示
枚举前置状态。
如果dp[i][m]成立,通过val枚举第i行:
dp[i+1][m+val] = true
dp[i+1][dp2[i]+val] = true
dp[i+1][x] = true,可以封装成立函数。枚举第i行,也可以封装成函数。
时间复杂度:O(mntarget)
动态规划的填表顺序
for i = 0 to m-1 枚举各例
动态规划的初始值
dp[0][0] = true,其它为false。
动态规划的返回值
dp1.back()[x]成立
min(min(abs(x-target)),abs(dp2.back()-target))
代码
核心代码
class Solution {
public:
int minimizeTheDifference(vector<vector<int>>& mat, int target) {
vector<int> pre(target);
pre[0] = true;
int iPre = INT_MAX/10;
for (const auto& v : mat) {
vector<int> cur(target);
int iCur = INT_MAX;
auto Add = [&](int curV) {
for (auto n : v) {
const int iNew = curV + n;
if (iNew >= target) {
iCur = min(iCur, iNew);
}
else {
cur[iNew] = true;
}
}
};
Add(iPre);
for (int i = 0; i < target; i++) {
if (pre[i]) { Add(i); }
}
swap(iPre, iCur);
pre.swap(cur);
}
int ans = (iPre - target);
for (int i = 0; i < target; i++) {
if (pre[i]) { ans = min(ans, target - i); }
}
return ans;
}
};
单元测试
vector<vector<int>> mat;
int target;
TEST_METHOD(TestMethod11)
{
mat = { {1,2,3},{4,5,6},{7,8,9} }, target = 13;
auto res = Solution().minimizeTheDifference(mat, target);
AssertEx(0, res);
}
TEST_METHOD(TestMethod12)
{
mat = { {1},{2},{3} }, target = 100;
auto res = Solution().minimizeTheDifference(mat, target);
AssertEx(94, res);
}
TEST_METHOD(TestMethod13)
{
mat = { {1,2,9,8,7} }, target = 6;
auto res = Solution().minimizeTheDifference(mat, target);
AssertEx(1, res);
}