原題地址

https://leetcode.com/problems/partition-equal-subset-sum/description/

題意

給一個(gè)非空數(shù)組，把數(shù)組劃分成和相同的兩部分

思路

對(duì)數(shù)組求和，若是奇數(shù)返回false，若是偶數(shù)自底向上建表
做的時(shí)候遇到的問(wèn)題：一開(kāi)始建表忘記先全都置成false了

代碼

class Solution {
public:
    int Sum(vector<int> & nums){
        int result=0;
        for(int i =0;i<nums.size();i++){
            result+=nums[i];
        }
        return result;
    }
    
    bool canPartition(vector<int>& nums) {
        int sum = Sum(nums);
        if(sum%2!=0){
            return false;
        }
        int target = sum/2;
        int n = nums.size();
        bool dp[target+1][n+1];
        memset(dp,false,sizeof(bool)*(target+1)*(n+1));
        for(int i =0;i<=n;i++){
            dp[0][i]=true;
        }
        for(int i =1;i<=target;i++){
            dp[i][0]=false;
        }
        for(int i =1;i<=target;i++){
            for(int j =1;j<=n;j++){
                if(i>=nums[j-1]){
                    dp[i][j]= dp[i-nums[j-1]][j-1];
                }
                if(dp[i][j]){
                    for(int k =j+1;k<=n;k++){
                        dp[i][k]=true;
                    }
                    break;
                }
                
            }
        }
        return dp[target][n]; 
    }
};