/**
* @param {number[]} nums
* @return {boolean}
* 第一种二位数组dp,dp[i][j]表示i个数字和能不能为j
* dp[i][j] = dp[i - 1][j] || (j >= nums[i] ? dp[i - 1][j - nums[i]] : false);
* 下面是nums[i-1], 因为nums[i-1]才表示第i个数字
*/
const canPartition1 = function (nums) {
let dp = [];
const sum = nums.reduce((a, b) => a + b);
const halfSum = sum / 2;
if ((sum & 1) === 1) {
return false;
}
for (let i = 0, ii = nums.length; i <= ii; ++i) {
dp[i] = [];
for (let j = 0; j <= halfSum; ++j) {
dp[i][j] = false;
}
}
for (let i = 0, ii = nums.length; i <= ii; ++i) {
dp[i][0] = true;
}
for (let i = 1, ii = nums.length; i <= ii; ++i) {
for (let j = 1; j <= halfSum; ++j) {
dp[i][j] = dp[i - 1][j] || (j >= nums[i - 1] ? dp[i - 1][j - nums[i - 1]] : false);
}
}
return dp[nums.length][halfSum]
};
// dp[i], 数字i是否是, 数组任意子集之和
const canPartition = function (nums) {
let dp = [true];
const sum = nums.reduce((a, b) => a + b);
const halfSum = sum / 2;
if ((sum & 1) === 1) {
return false;
}
for (let j = 1, jj = halfSum; j <= jj; ++j) {
dp[j] = false;
}
for (let i = 0, ii = nums.length; i < ii; ++i) {
// for (let j = 1, jj = halfSum; j <= jj; ++j) { 正着写不行, 如果有元素值为1,则所有的dp[j]的值为true
for (let j = halfSum; j > 0; --j) { // 原因是因为倒着写的话dp[i] = dp[i-1] 会从大到小,最后才会触碰到dp[0] = ture这个特殊的边界条件
// console.log(dp[j]);
if (j >= nums[i]) {
// console.log(dp[j - nums[i]]);
dp[j] = dp[j] || dp[j - nums[i]];
}
}
}
console.log(dp);
return dp[halfSum];
};