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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/