动态规划-背包问题——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];}
};

代码解析 

代码优化