【416】动态规划第三弹：分割等和子集

84 阅读 0 评论 56 点赞

我是靠谱客的博主忧郁石头，最近开发中收集的这篇文章主要介绍【416】动态规划第三弹：分割等和子集，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

谈起动态规划，痛苦的回忆又涌上心头，大三算法课受够了它的折磨，没想到，现在为了刷leetcode，又要重新捡起这一块的知识，说多了都是泪啊~还是跟着代码随想录的Carl老哥刷刷题吧。今天这个题目是Leetcode上的416题：分割等和子集，题目描述如下。

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

这个题目不难理解，即给你一个数组，判断能否从数组中找到若干个数，使得它们的和等于数组中所有元素和的一半。

读完题目，是不是感觉可以直接暴力！下面是暴力的JS代码（回溯法）。

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var dfs = function(target,nums,j){
    if(target==0) return true;
    if(j == nums.length) return false;
    if (target < 0) return false;
    return dfs(target - nums[j],nums,j+1) || dfs(target,nums,j+1);
}
var canPartition = function(nums) {
    let sum = 0;
    // 给数组排个序
    nums.sort();
    for(let i = 0;i<nums.length;i++){
        sum += nums[i];
    }
    // 如果不能整除，直接放回false
    if(sum % 2 == 1) return false;
    let target = sum / 2;
    if(nums[0] > target) return false;
    if(nums[0] == target) return true;
    return dfs(target,nums,0);
};

然鹅，超出时间限制。

所以还是想想其他时间复杂度低的方法吧。那就是动态规划！

其实将这个题目与0-1背包问题联系起来想，你会发现，这不就是一个0-1背包问题吗？

将题目转换为0-1背包的描述即为：判断能否用cost数组、value数组刚好填充一个容量为sum(value/2)的背包。

（以下是状态压缩之后的dp数组）

那么，首先定义一下dp数组的含义。dp[i]表示容量为i的背包所能够取到的最大价值

状态转移方程为：dp[i] = max(dp[i] , dp[i - weight[j] ] + value[j])

最后的判断条件即为dp[target] ?= target

（思路当然不是我想出来的，尔等菜鸡，什么时候才能像Carl哥这么强）

下面根据思路，写一下代码（好吧，其实写代码的过程很不顺畅，参考了carl哥的代码）。

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
    // 首先求和
    let sum = 0;
    for (let i=0;i<nums.length;i++){
        sum += nums[i];
    }
    if (sum%2 == 1) return false;
    // 初始化目标
    let target = sum/2;
    // 初始化dp数组
    let dp = new Array(target + 1).fill(0);

    for(let i = 0; i < nums.length; i++){
        for(let j = target; j >= nums[i]; j--){
            dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);
        }
    }
    if(dp[target] == target) return true;
    return false;
};

下面是参考的carl哥的代码。

var canPartition = function(nums) {
    const sum = (nums.reduce((p, v) => p + v));
    if (sum & 1) return false;
    const dp = Array(sum / 2 + 1).fill(0);
    for(let i = 0; i < nums.length; i++) {
        for(let j = sum / 2; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            if (dp[j] === sum / 2) {
                return true;
            }
        }
    }
    return dp[sum / 2] === sum / 2;
};

作者：代码随想录
链接：https://leetcode.cn/problems/partition-equal-subset-sum/solutions/553978/bang-ni-ba-0-1bei-bao-xue-ge-tong-tou-by-px33/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2022.12.2 更新二维dp数组版本（调试了半天，结果发现还是对javascript基础不熟悉啊，踩了一个大坑，另开一篇说吧）

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  let sum = 0;
  for (const item of nums) sum += item;
  if (sum % 2 == 1) return false;
  const target = sum / 2;

  // 用二维dp数组来解决这个问题
  // 首先定义value数组和weight数组
  let weight = nums.slice(0);
  let value = nums.slice(0);
  let dp = new Array(nums.length)
    .fill()
    .map(() => new Array(target + 1).fill(0));
  // 初始化dp数组
  for (let j = weight[0]; j <= target; j++) dp[0][j] = weight[0];
  // console.log(dp);
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j <= target; j++) {
      if (j < nums[i]) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
      }
      // console.log(i,j,dp);
    }
  }
  // console.log(dp);
  // console.log(dp[nums.length-1][target]);

  if (dp[nums.length - 1][target] == target) return true;
  return false;
};