本文介绍: 采用一维线性数组dp[j],定义为容量为j的背包,所装的数字大小最大为j。
416. 分割等和子集
题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 100
题目分析
采用01背包的方法,
01背包中,dp[j] 表示: 容量为j的背包,所背的物品价值最大可以为dp[j]。
动归五部曲
1. 定义dp数组
采用一维线性数组dp[j],定义为容量为j的背包,所装的数字大小最大为j。
2. 确定dp数组的递推公式
要知道在dp[j]时,背包有两种情况,
拿输入数组 [1, 5, 11, 5],举例, dp[7] 只能等于 6,因为 只能放进 1 和 5,没有装满。
而dp[6] 就可以等于6了,放进1 和 5,那么dp[6] == 6,说明背包装满了。
3. dp数组的初始化
dp[0]放不下东西初始化为0;
因为要通过Math.max()函数比较,因此其他数据也得初始化0。
java中会自动将数组初始化为0。
4. 确定dp数组的遍历顺序
5.举例说明
优化
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。