算法篇——动态规划 01背包问题 (js版)_js背包算法

416. 分割等和子集

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

链接：力扣

解题思路：

这道题看似是比较简单的背包问题：

首先可以通过判断数组和是否是偶数，因为如果是奇数是必然不可能拆分成两个数组的，直接返回false；

if(nums.length == 1) return false
var sum = 0
// 数组求和
for(var i = 0; i < nums.length; i++) {
    sum += nums[i]
}
// 如果相加不是偶数说明不可能拆成相等的两个数组
if(sum % 2 != 0) return false

接着获取sum / 2，也就是target，我们利用一个新的方法：getSum，对元素和它的索引指针进行遍历

// 目标值是当前和的一半
var target = sum / 2
// map 用来遍历元素，可记录元素状态，相比循环更快，防止超时
const map = new Map()

这里也是有两个临界判断的：指针是否会越界，数组中的数据项之和是否会超出 target，否则就是可以拆分的

// 越界
if(i == nums.length || cur > target) return false
// 可拆分
if(cur == target) return true

但同时还需要判断不连续的数据项是否满足

var key = cur + '+' + i
// 如果map中有对应的缓存值，直接get拿出使用
if(map.has(key)) {
   return map.get(key)
}
// 如果需要当前的项，就加入当前的和，移动指针到下一位
// 如果不需要当前的项，就直接移动指针到下一位
const res = getSum(cur + nums[i], i + 1) || getSum(cur, i + 1)
// 避免重复遍历元素，存入map中，可直接对应查找
map.set(key, res)
return res

这里调用方法时，主要考虑：如果需要当前的项，就加入当前的和，移动指针到下一位；如果不需要当前的项，就直接移动指针到下一位

并且利用map的好处就是可以防止重复遍历计算元素，提高了时间性能

下面是完整代码：

var canPartition = function(nums) {
    if(nums.length == 1) return false
    var sum = 0
    // 数组求和
    for(var i = 0; i < nums.length; i++) {
        sum += nums[i]
    }
    // 如果相加不是偶数说明不可能拆成相等的两个数组
    if(sum % 2 != 0) return false 
    // 目标值是当前和的一半
    var target = sum / 2
    // map 用来遍历元素，可记录元素状态，相比循环更快，防止超时
    const map = new Map()
    // cur： 当前和，i：指针
    const getSum = (cur, i) => {
        // 越界
        if(i == nums.length || cur > target) return false
        // 可拆分
        if(cur == target) return true
        var key = cur + '+' + i
        // 如果map中有对应的缓存值，直接get拿出使用
        if(map.has(key)) {
            return map.get(key)
        }
        // 如果需要当前的项，就加入当前的和，移动指针到下一位
        // 如果不需要当前的项，就直接移动指针到下一位
        const res = getSum(cur + nums[i], i + 1) || getSum(cur, i + 1)
        // 避免重复遍历元素，存入map中，可直接对应查找
        map.set(key, res)
        return res
    }
    return getSum(0, 0) // 递归入口，从第一个元素开始遍历
};

以上的代码时间消耗很大，下面利用动态规划的方法，与上面的思路类似，也是要进行如下步骤：（注意看图中的红框内容）

1.根据数组的长度 nums.length 判断数组是否可以被划分：如果 n=1，直接返回 false

2.计算整个数组的元素和 sum 以及最大元素 maxNum：如果 sum 是奇数，直接返回 false；反之，target= sum / 2

3.判断是否数组中是否存在元素的和等于 target。如果 maxNum > target，则除了 maxNum 以外的所有元素之和一定小于 target，直接返回false，完整代码如下：

var canPartition = function(nums) {
    // 一个元素无法拆分成两个数组
    if(nums.length == 1) return false
    var sum = 0, max = 0
    for(var i = 0; i < nums.length; i++) {
        sum += nums[i]
        // 得到最大元素
        max = max > nums[i] ? max : nums[i]
    }
    // 数组和是奇数
    if(sum % 2 != 0) return false 
    // 目标值是数组和的一半
    var target = sum / 2
    // 如果 max > target，则除了 max 以外的所有元素之和一定小于 target
    if(max > target) return false
    // 定义长度为 target+1 的数组，并赋值数组的初始值
    // 对于给定的数组 nums，能否选取其中一部分元素，使得它们的总和恰好等于 target 
    // 初始时，将数组 dp 初始化为全零，表示当前还没有任何元素可以选取
    const dp = new Array(target+1).fill(0)
    // 外层循环变量 i 表示遍历数组 nums 的索引，内层循环变量 j 表示当前的目标和（从大到小递减）
    for(var i = 0; i < nums.length; i++) {
        for(var j = target; j >= nums[i]; j--) {
            // 如果 nums[i] 可以选，则更新 dp[j]，意味着 dp[j - nums[i]] + nums[i]：前一个目标和 j - nums[i] 的最优结果加上当前选的 nums[i]
            // 如果 nums[i] 不可选，则 dp[j] 保持不变
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])
            // 判断 dp[j] 是否等于 target：如果相等，返回 true，否则继续遍历
            if(dp[j] == target) return true
        }
    }
    return dp[target] == target
}

1049. 最后一块石头的重量 II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

链接：力扣

这道题的思路和上一题的思路类似，让石头分成重量相同的两堆，相撞后剩下的石头最小 

var lastStoneWeightII = function(stones) {
    // 如果只有一块石头，直接返回当前石头的重量
    if(stones.length == 1) return stones[0]
    var sum = 0
    for(var i = 0; i < stones.length; i++) {
        sum += stones[i]
    }
    var target = Math.floor(sum / 2)
    var dp = new Array(target+1).fill(0)
    for(var i = 0; i < stones.length; i++) {
        for(var j = target; j >= stones[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j- stones[i]] + stones[i])
        }
    }
    return sum - 2 * dp[target]
}

494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目

链接：力扣 

解题思路：本题不同于上面两题的地方在于，这题需要求出有多少种方法，前面的递推公式都是

dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])

但这道题的是把 所有的 dp[j - nums[i]] 累加起来，这也是组合类问题的共性，即 

dp[j] += dp[j - nums[i]]

如果数组长度是1 ，考虑这个元素与 target 的大小值，如果不等于 target 的绝对值，返回0，反之返回1

// 如果数组长度是1
if(nums.length == 1) {
   if(nums[0] == Math.abs(target)) return 1
   else return 0
}

如果 目标值的绝对值 大于 数组元素之和 sum，无法找到满足条件的方案；如果 目标值与元素之和 的和 取余为非零值，直接返回 0，因为如果将数组分为两个子集，它们的和必须相等，而加法操作结果除以 2 的余数只能是 0 或 1

// 目标值的绝对值大于数组元素之和 sum，无法找到满足条件的方案
// 如果 目标值与元素之和 的和 取余为非零值，直接返回 0
if(Math.abs(target) > sum || (target + sum) % 2) return 0
var mid = (target + sum) / 2
var dp = new Array(mid+1).fill(0)

下面是完整的代码：

var findTargetSumWays = function(nums, target) {
    // 如果数组长度是1
    if(nums.length == 1) {
        if(nums[0] == Math.abs(target)) return 1
        else return 0
    }
    var sum = 0
    for(var i = 0; i < nums.length; i++) {
        sum += nums[i]
    }
    // 目标值的绝对值大于数组元素之和 sum，无法找到满足条件的方案
    // 如果 目标值与元素之和 的和 取余为非零值，直接返回 0
    if(Math.abs(target) > sum || (target + sum) % 2) return 0
    var mid = (target + sum) / 2
    var dp = new Array(mid+1).fill(0)
    // 这里初值赋值为 1，是因为如果为 0，则递归下来，只可能有 1种方案，因为始终为 0
    dp[0] = 1
    for(var i = 0; i < nums.length; i++) {
        for(var j = mid; j >= nums[i]; j--) {
            dp[j] += dp[j - nums[i]]
        }
    }
    return dp[mid]
}

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

链接：力扣

解题思路：

这里的二维数组定义dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j] 

01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

因此此题中 dp[i][j] 可以由前一个 strs 中的字符串推出，strs里的字符串有 num0 个0，num1 个1

dp[i][j] 是 dp[i - num0][j - num1] + 1。然后遍历取 dp[i][j] 的最大值，递推公式：

dp[i][j] = max(dp[i][j], dp[i - num0][j - num1] + 1)

var findMaxForm = function(strs, m, n) {
    const dp = Array(m+1).fill(0).map(() => Array(n+1).fill(0)) 
    for(const str of strs) {
        let num0 = 0
        let num1 = 0
        for(const s of str) {
            // 对字符串中的 0 和 1 计数
            if(s == '0') num0++
            else num1++
        }
        // 使用两个倒序循环，从 m 到 numOfZeros，从 n 到 numOfOnes，更新 dp[i][j] 的值
        for(let i = m; i >= num0; i--) {
            for(let j = n; j >= num1; j--) {
                // 如果加入当前字符串，则更新 dp[i][j] 的值为 之前 dp[i - numOfZeros][j - numOfOnes] 的值加1
                // 如果不加入当前字符串，则 dp[i][j] 不变
                dp[i][j] = Math.max(dp[i][j], dp[i - num0][j - num1] + 1)
            }
        }
    }
    return dp[m][n]
}