当前位置:   article > 正文

力扣416题:分割等和子集_力扣,俩子集和相等

力扣,俩子集和相等

力扣416题:分割等和子集

题目描述

给你一个 只包含正整数非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

输入输出样例

输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
  • 1
  • 2
  • 3
输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。
  • 1
  • 2
  • 3
  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

解法:动态规划

bool canPartition(vector<int>&nums)
    {   
        //对数组的初始情况进行判断
        if(nums.empty())
        {
            return false;
        }

        int length=nums.size();
        int sum=0;

        //计算数组中所有的元素的总和,若总和为奇数就代表该数组无法被分割成两个等和子集
        for(int num:nums)
        {
            sum+=num;
        }

        if(sum%2==1)
        {
            return false;
        }

        //因此设置目标值为sum/2,因为只要数组的一部分子集满住总和的一半,另一部分自然而然也能满足
        int target=sum/2;

        //创建动态规划数组,行,代表数组内元素的索引,列,代表目标值
        vector<vector<bool>>dp(length,vector<bool>(target+1));

        //对动态规划数组进行初始化
        //先填表格中的第0行,因为第一个数只能让容积为他的背包恰好被装满
        if(nums[0]<=target)
        {
            dp[0][nums[0]]=true;
        }

        //建立动态规划的状态转移方程
        for(int i=1;i<length;i++)
        {
            for(int j=0;j<=target;j++)
            {
                // 由题意分析出来,状态转移方程为
                //dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i]] 其中如果nums[i]=j,直接便可返回true

                dp[i][j]=dp[i-1][j];

                if(nums[i]==j)
                {
                    dp[i][j]=true;
                    continue;
                } 
                if(nums[i]<j)
                {
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]];
                }
            }
        }
        return dp[length-1][target];
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59

动态规划:优化状态转移方程

 //修改动态转移方程
        bool canPartition2(vector<int>&nums)
    {   
        //对数组的初始情况进行判断
        if(nums.empty())
        {
            return false;
        }

        int length=nums.size();
        int sum=0;

        //计算数组中所有的元素的总和,若总和为奇数就代表该数组无法被分割成两个等和子集
        for(int num:nums)
        {
            sum+=num;
        }

        if(sum%2==1)
        {
            return false;
        }

        //因此设置目标值为sum/2,因为只要数组的一部分子集满住总和的一半,另一部分自然而然也能满足
        int target=sum/2;

        //创建动态规划数组,行,代表数组内元素的索引,列,代表目标值
        vector<vector<bool>>dp(length,vector<bool>(target+1));

        //对动态规划数组进行初始化
        //初始化dp[0][0]=true;

        dp[0][0]=true;


        //先填表格中的第0行,因为第一个数只能让容积为他的背包恰好被装满
        if(nums[0]<=target)
        {
            dp[0][nums[0]]=true;
        }

        //建立动态规划的状态转移方程
        for(int i=1;i<length;i++)
        {
            for(int j=0;j<=target;j++)
            {
                // 由题意分析出来,状态转移方程为
                //dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i]] 其中如果nums[i]=j,直接便可返回true

                dp[i][j]=dp[i-1][j];


                if(nums[i]<=j)
                {
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]];
                }
            }
        }
        return dp[length-1][target];
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

动态规划,优化空间

 //  优化空间
    //将状态数组从二维优化成一维    //修改动态转移方程
    //从后往前遍历进行实现
    bool canPartition3(vector<int>&nums)
    {   
        //对数组的初始情况进行判断
        if(nums.empty())
        {
            return false;
        }

        int length=nums.size();
        int sum=0;

        //计算数组中所有的元素的总和,若总和为奇数就代表该数组无法被分割成两个等和子集
        for(int num:nums)
        {
            sum+=num;
        }

        if(sum%2==1)
        {
            return false;
        }

        //因此设置目标值为sum/2,因为只要数组的一部分子集满住总和的一半,另一部分自然而然也能满足
        int target=sum/2;

        //创建动态规划数组,行,代表目标值

        vector<bool>dp(target+1);

        //对动态规划数组进行初始化
        //初始化dp[0][0]=true;

        dp[0]=true;


        //先填表格中的第0行,因为第一个数只能让容积为他的背包恰好被装满
        if(nums[0]<=target)
        {
            dp[nums[0]]=true;
        }

        //建立动态规划的状态转移方程
        for(int i=1;i<length;i++)
        {
            for(int j=target;nums[i]<=j;j--)
            {
                // 由题意分析出来,状态转移方程为
                //dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i]] 其中如果nums[i]=j,直接便可返回true

                if(dp[target])
                {
                    return true;
                }
                dp[j]=(dp[j]||dp[j-nums[i]]);
            }
        }
        return dp[target];
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/黑客灵魂/article/detail/744942
推荐阅读
相关标签
  

闽ICP备14008679号