提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【动态规划】LeetCode 题解：416-分割等和子集

LeetCode规划 动态 分割 题解 子集
2023-06-13 09:16:07 时间

大家好，我是前端西瓜哥，有三个月没做算法题了，这次就来做一道动态规划中难度较低的题。

题目

给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

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

题目来源：

https://leetcode.cn/problems/partition-equal-subset-sum

题解

动态规划，它的模型需要符合 多阶段决策最优解模型，即要推导出最后的结果，它需要经历多个阶段。

比如经典的跳楼梯，假如你要跳到第 7 阶梯的楼梯，你需要先知道跳到第 5 和第 6 阶梯需要走的步数。

还比如 0-1 背包问题，我们在决策是否要放入第 n 个物品，我们需要知道上一个决策完成后，书包的所有可能的重量。

这些都是 阶段。我们让多个选择同时并行发生，产生一个个阶段，并记下状态，给下一个状态使用。

我们回到正题。

题目意思是问能否将数组拆分成两个子数组，这两个子数组的和相等。

其实这就等价于，数组元素中是否存在一个子数组，它的和为原数组的总和除以 2，这时它就变成了经典 0-1 背包问题，你需要决策每个阶段是否放入特定的数组元素，直到刚好为总和除以 2。

0-1 背包问题，有在书包有最大承重情况下，求放入物体的最大重量。或是提升到二维，求放入物体的最大价值。 这道题属于前者。

先看完整的题解：

function canPartition(nums) {
  const sum = nums.reduce((sum, curr) => sum + curr, 0);
  if (sum % 2 === 1) return false; // 奇数，无法分成两份
  const half = sum / 2;

  // 提前判断特殊情况，避免后面无谓的初始化，可省略
  if (nums[0] === half) return true;

  // 变成 0-1 背包问题，就是一个个决策是否放入，直到刚好为目标大小

  // 初始化 dp 数组
  const dp = new Array(nums.length);
  for (let i = 0; i < dp.length; i++) {
    dp[i] = new Array(half + 1).fill(false);
  }
  dp[0][0] = true;
  if (nums[0] <= half) {
    dp[0][nums[0]] = true;
  }

  // 多个决策阶段
  for (let i = 1; i < dp.length; i++) {
    // 决策是否加入某元素
    for (let j = 0; j < dp[i].length; j++) {
      if (dp[i - 1][j] === true) {
        dp[i][j] = true; // 元素不加入
        if (j + nums[i] < half) { // 元素加入
          dp[i][j + nums[i]] = true;
        } else if (j + nums[i] === half) { // 找到了
          return true;
        }
      }
    }
  }
  return false;
};

这里的要点是构建一个二维布尔值数组 dp，用来保存每个阶段的状态，对于 dp[i][j]，i 表示决策第 i 个元素是否被放入，j 表示子数组总和。

所以 dp[i][j] 的意思就是在决策第 i 个元素的阶段，是否存在一种可能，让总和为 j。

因为当前阶段需要靠上一个阶段推导，所以我们需要初始化第一阶段的状态：

// 初始化 dp 数组
const dp = new Array(nums.length);
for (let i = 0; i < dp.length; i++) {
  dp[i] = new Array(half + 1).fill(false);
}
dp[0][0] = true;
if (nums[0] <= half) {
  dp[0][nums[0]] = true;
}

然后推导下一个阶段时，就遍历上一阶段的值，如果为 true，就基于它决策加入当前元素和不加入当前元素后得到的新的总和，在对应的位置标记为 true，直到和为目标值。

// 多个决策阶段
for (let i = 1; i < dp.length; i++) {
  // 决策是否加入某元素
  for (let j = 0; j < dp[i].length; j++) {
    if (dp[i - 1][j] === true) {
      dp[i][j] = true; // 元素不加入
      if (j + nums[i] < half) { // 元素加入
        dp[i][j + nums[i]] = true;
      } else if (j + nums[i] === half) { // 找到了
        return true;
      }
    }
  }
}

其实还可以做内存优化，将二维数组转换为一维数组，这需要用从后往前遍历数组的技巧。

这里还用二维数组的解法，是因为它还是比较经典的，有普适性，适合用于讲解。一些题目中，甚至能将优化为几个变量，比如跳楼梯。

结尾

动态规划，是有一定难度的算法题类型，也是面试大厂时比较常看到的题目，有掌握的必要性。

我是前端西瓜哥，关注我，学习更多前端知识。

相关文章