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

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

公司主营业务：网站设计、网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。成都创新互联公司是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联公司推出资兴免费做网站回馈大家。

题目

给你一个只包含正整数的非空数组 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; 
  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。

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

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;
      }
    }
  }
}

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

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

结尾

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

当前文章：【动态规划】LeetCode题解：416-分割等和子集
标题路径：http://www.mswzjz.cn/qtweb/news19/19269.html

攀枝花网站建设、攀枝花网站运维推广公司-贝锐智能，是专注品牌与效果的网络营销公司；服务项目有等

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：贝锐智能

贝锐智能技术为您推荐以下文章