LeetCode 416 Partition Equal Subset Sum
动态规划问题 LeetCode 2020-03-11 17:37:20 2022-02-19 13:11:55 826 次浏览概述
https://leetcode.com/problems/partition-equal-subset-sum/
第一种状态定义
dp[i][s]
将题目所给的数字数组分为两部分，左边的部分我们还没确定，右边的部分我们已经确定要放到哪一个子集里，将左边的部分的数字个数记为 i。
其中一个子集里元素的和 s，有了 i 和 s 之后我们就可以算出另一个子集中元素的和。
在这种状态定义下，需要消耗大量的空间，原因就在于 s 的范围为 0 ~ 元素个数*元素的最大可能值。
第二种状态定义
仔细分析题目，nums 数组是给定的，我们需要将其分为相等的两个部分，那么分出来的值也是确定的，即 sum(nums)/2。
定义状态 dp[j] 表示值 j 能否从 nums 的子集中构建出来（里面存储的是一个布尔值）。
那答案就是 dp[sum(nums)/2]。
上面是 2020 年时的笔记，思路是有问题的，你要怎么从子问题的解推出父问题的解呢？
我们应当同时记录当前和以及位置。
考虑到和的稀疏性，用 map 好了。
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (auto& num : nums) sum += num;
if (sum % 2 != 0) return false;
unordered_map<int, vector<int>> dp;
return helper(dp, nums, sum / 2, 0);
}
bool helper(unordered_map<int, vector<int>>& dp, vector<int>& nums, int s, int i) {
if (s == 0) return true;
if (s < 0 || i >= nums.size()) return false;
if (dp.count(s) == 0) {
vector<int> t(nums.size(), 0);
dp[s] = t;
}
if (dp[s][i] != 0) return dp[s][i] == 1;
if (helper(dp, nums, s - nums[i], i + 1) || helper(dp, nums, s, i + 1)) {
dp[s][i] = 1;
} else {
dp[s][i] = 2;
}
return dp[s][i] == 1;
}
};