动态规划-背包问题——416.分割等和子集

1.题目解析

题目来源

416.分割等和子集——力扣

测试用例 

2.算法原理

1.状态表示

这里背包问题基本上和母题的思路大相径庭，母题请见 [模板]01.背包 ，这里的状态表示与装满背包的情况类似，第二个下标就是当选择的物品体积直接等于j时是否可以装入"背包"，本题是求是否可以将一个数组分为大小相等的两部分，不妨变换思路，求出是否可以找一些数字的和等于该数组的一半，即

dp[i][j]：选择[1,i]区间的物品，此时总"体积"完全等于j时是否可以装入"背包"

2.状态转移方程

状态转移方程需要判断最后一个位置是否可以装入"背包"，以此来判断此时位置的状态

1.当不选择当前位置：dp[i][j] = dp[i-1][j]，不选择则"体积"不变，也就是j不变

2.选择当前位置：需要找到前面位置是否存在，也就是dp[i-1][j-nums[i-1]]，注意判断j>=nums[i-1]，不然就不能使用该位置的状态

3.初始化

开辟了虚拟位置，需要对虚拟位置进行初始化

4.填表顺序

从上到下，每一行从左到右

5.返回值 

返回最后一个位置的dp值

3.实战代码

class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
        int m = nums.size();
        int sum = 0;
        for(auto e : nums)
        {
            sum += e;
        }    
        int aim = sum / 2;

        if(sum % 2 == 1)
        {
            return false;
        }
        vector<vector<bool>> dp(m+1,vector<bool>(aim+1));
        for(int i = 0;i <= m;i++)
        {
            dp[i][0] = true;
        }

        for(int i = 1;i <= m;i++)
        {
            for(int j = 1;j <= aim;j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1])
                {
                    dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[m][aim];
    }
};

代码解析 

代码优化