LeetCode 416. Partition Equal Subset Sum

题解

这题就是01背包,特征就是选与不选对吧。
但是这题又有点变化,不是算max min 或者方案数,而是确定解是否存在,料想dp应为bool型。

dp[ i , j ] : 代表在前i个数中,是否能取得和为j。
转移方程很合理:
dp [i , j] = d[ i-1, j ] || dp [ i-1, j - nums[i] ] // 取 或 不取

ps: 注意dp[0 0] = true。显然可以优化到一维。还有更快的解法。


Code
class Solution {
public:
    bool dp[20001];
    bool canPartition(vectorint nums) {
        int sum=0;
        for(int t:nums) sum+=t;
        if(sum%2 == 1) return false;
        sum=1;
        dp[0] = true;
        for(int num:nums)
            for(int i=sum;i=num;i--)
                dp[i] = dp[i] || dp[i-num];
        
        return dp[sum];
    }
};
最新回复(0)
/jishuJi6cr9I9_2BuJ5CclgDsea5BgBpdBpTZKfoiF4zQ_3D_3D4858369
8 简首页