网站宣传软文,南京网站seo服务,东莞房价2021最新价格走势,php网站开发意思1.题目解析 题目来源 416.分割等和子集——力扣 测试用例 2.算法原理 1.状态表示
这里背包问题基本上和母题的思路大相径庭#xff0c;母题请见 [模板]01.背包 #xff0c;这里的状态表示与装满背包的情况类似#xff0c;第二个下标就是当选择的物品体积直接等于j时是否可… 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]]注意判断jnums[i-1]不然就不能使用该位置的状态 3.初始化
开辟了虚拟位置需要对虚拟位置进行初始化 4.填表顺序
从上到下每一行从左到右
5.返回值
返回最后一个位置的dp值 3.实战代码 class Solution {
public:bool canPartition(vectorint nums) {int m nums.size();int sum 0;for(auto e : nums){sum e;} int aim sum / 2;if(sum % 2 1){return false;}vectorvectorbool dp(m1,vectorbool(aim1));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];}
}; 代码解析 代码优化
