「每日LeetCode」2020年10月11日

本文最后更新于：2023年3月19日 晚上

Lt416. 分割等和子集,动态规划

416. 分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 200

示例 1:

1
2
3
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例  2:

1
2
3
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

思路

动态规划-二维矩阵

具体过程可以参考官方题解分割等和子集

  1. 如果数组长度小于等于 1，直接返回 false
  2. 求数组的和及数组内元素的最大值，求和完毕，求出 target=sum/2，将问题转化为求数组中是否存在一个子集的和为 target
    1. 如果 target 不能整除 2，则不存在结果，返回 false
    2. 如果 target 比数组内元素的最大值小，则不存在结果，返回 false
  3. 设置一个二维矩阵，用于动态规划，问题现在变成了0-1 背包问题，横坐标为 target 值，纵坐标为原数组下标的取值范围（可以为 0 个）
    1. 首先将第一列，即 target=0，不管哪一行都可以取 0 个得到 target=0，所以第一列都设为 true
    2. 对第一行来说，即只有 nums[0]这一个元素，target 只能取到 0 或者 nums[0]本身，所以将dp[0][nums[0]]设为 true
    3. 遍历剩余的行及元素，从第二行开始，相当于背包问题添加了新的物品再来判断情况，及原数组的第二个元素，之后的每行都设当前的元素为num=nums[i]，再对每一列 j，即能否取到当前列的值进行判断：
      1. 如果 num>j，则说明不能取当前的元素，能否取到当前 j 的值，只看前一行对应的位置的值，直接令 dp[i][j]= dp[i-1][j]即可。
      2. 如果 num<=j，这说明可以取到当前的元素，能否取到当前 j 的值，取决于前一行对应的位置是否可取或者取了当前数值以后，剩下的值在前一行是否可取，所以对应的表达式为 dp[i][j]= dp[i-1][j] || dp[i-1][j-num]
  4. dp 矩阵生成完毕以后，直接返回矩阵右下角的值即可，右下角的值即意味着转化后的问题数组中是否存在一个子集的和为 target

动态规划-一维矩阵优化

具体过程可以参考官方题解分割等和子集

  1. 如果数组长度小于等于 1，直接返回 false
  2. 求数组的和及数组内元素的最大值，求和完毕，求出 target=sum/2，将问题转化为求数组中是否存在一个子集的和为 target
    1. 如果 target 不能整除 2，则不存在结果，返回 false
    2. 如果 target 比数组内元素的最大值小，则不存在结果，返回 false
  3. 由之前可以看到，当前行的情况只取决于上一行，所以可以对矩阵进行优化，简化为一维矩阵，从尾部开始判断，就不会产生影响
    1. 对于任何元素都可取 0 个令 target=0，所以先令dp[0]=true
    2. 遍历每个元素，对于每个元素来说，都从 dp 的最后一个开始判断，到当前元素的值为止即可，小于当前元素的值是不会发生变化的
  4. dp 矩阵生成完毕以后，直接返回矩阵最后一个元素的值即可

解答

动态规划-二维矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  if (nums.length <= 1) return false;
  let max = nums[0];
  const sum = nums.reduce((a, b) => {
    max = Math.max(max, b);
    return a + b;
  }, 0);
  const target = sum / 2;
  if (sum % 2 !== 0 || max > target) return false;
  const dp = new Array(nums.length)
    .fill(0)
    .map((v) => new Array(target).fill(false));
  for (let i = 0; i < nums.length; i++) {
    dp[i][0] = true;
  }
  dp[0][nums[0]] = true;
  for (let i = 1; i < nums.length; i++) {
    const num = nums[i];
    for (let j = 1; j <= target; j++) {
      if (num > j) dp[i][j] = dp[i - 1][j];
      else dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
    }
  }
  return dp[nums.length - 1][target];
};

动态规划-一维矩阵优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  if (nums.length <= 1) return false;
  let max = nums[0];
  const sum = nums.reduce((a, b) => {
    max = Math.max(max, b);
    return a + b;
  }, 0);
  const target = sum / 2;
  if (sum % 2 !== 0 || max > target) return false;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
  return dp[target];
};