My Muri Life

切换主题

本页目录

背包问题篇 ​

0-1背包 ​

  1. 什么是0-1背包呢？

我们有n件物品和一个容量为C的背包，记第i件物品的重量为w[i]，价值为v[i]，求将哪些物品装入背包可使价值总和最大？
如果限定每件物品最多只能选取1次（即0或1次），则问题称为0-1背包问题。

  1. 通用情况：

    • 状态定义：dp[i][j] = x，表示前i件物品放入容量为j的背包时，可以获取的最大价值为x；
    • base case：根据情况分析；
    • 状态转移方程：dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])，其中j - w[i]必须大于等于0。

  2. 遍历技巧：

    JavaScript
    // 1. 非组合问题(包括不需考虑元素之间的顺序的组合问题)
for (const num of nums) { // 外层循环遍历 物品
  for (let j = cap; j >= num; j--) { // 内层循环遍历 背包（0-1背包倒序遍历）
    // 状态转移方程
  }
}
// 2. 组合问题(需考虑元素之间的顺序)
for (let j = num; j <= cap; j++) { // 外层循环遍历 背包
  for (const num of nums) { // 内层循环遍历 物品
    // 状态转移方程
  }
}

  3. 0-1背包常见的几类问题：

    • 组合问题 ==> 状态转移方程：dp[j] += dp[j-num]；
    • 存在问题 ==> 状态转移方程：dp[j] ||= dp[j-num]；
    • 最值问题 ==> 状态转移方程：dp[j] = Math.max(dp[j], dp[j-num] + 1) or Math.min(dp[j], dp[j-num] + 1)。

分割等和子集 ​

剑指 Offer II 101. 分割等和子集

  • 状态定义：dp[i][j] = true/false，表示从[0, i]这个子区间内挑选一些正整数(每个数只能用一次)，使得这些数的和恰好等于/不等于j；
  • base case：dp[0][0] = true；
  • 状态转移方程：dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]]。
JavaScript
const canPartition = nums => {
  const sum = nums.reduce((acc, cur) => acc + cur, 0)
  if (sum & 1) return false
  const cap = sum >> 1
  const dp = Array(cap + 1).fill(0)
  dp[0] = true
  for (const num of nums) {
    for (let j = cap; j >= num; j--) {
      dp[j] ||= dp[j - num]
    }
  }
  return dp[cap]
}

时间复杂度：O(n*cap)；空间复杂度：O(cap)。

目标和 ​

剑指 Offer II 102. 目标和

  • 状态定义：dp[i][j] = x，表示前i个数能凑出和为j的方法有x种；
  • base case：dp[0][0] = 1；
  • 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i-1][j - num[i-1]]。
JavaScript
const findTargetSumWays = (nums, target) => {
  const sum = nums.reduce((acc, cur) => acc + cur, target)
  if (sum & 1) return false
  const cap = sum >> 1
  const dp = Array(cap + 1).fill(0)
  dp[0] = 1
  for (const num of nums) {
    for (let j = cap; j >= num; j--) {
      dp[j] += dp[j - num]
    }
  }
  return dp[cap]
}

时间复杂度：O(n*cap)；空间复杂度：O(cap)。

最后一块石头的重量 II ​

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

  • 状态定义：dp[i][j] = x，表示在前i块石头中选取石头且总重量不超过j的情况下的最大总重量为x；
  • base case：dp[0][0] = 0；
  • 状态转移方程：dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - stones[i-1]] + stones[i-1])。
JavaScript
const lastStoneWeightII = stones => {
  let sum = stones.reduce((acc, cur) => acc + cur, 0)
  const cap = sum >> 1
  const dp = Array(cap + 1).fill(0)
  for (const stone of stones) {
    for (let j = cap; j >= stone; j--) {
      dp[j] = Math.max(dp[j], dp[j - stone] + stone)
    }
  }
  return sum - 2 * dp[cap]
}

时间复杂度：O(n*cap)；空间复杂度：O(cap)。

一和零 ​

474. 一和零

  • 状态定义：dp[i][j][k] = x，表示前i个字符串中选出若干个，在使得其中0的数目不超过j、1的数目不超过k的情况下能够选出的最多的字符串数目为x；
  • base case：dp[0][0][0] = 0；
  • 状态转移方程：dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j - cntZero][k - cntOne] + 1)。
JavaScript
const findMaxForm = (strs, m, n) => {
  const cnt = (str, num = 0) => {
    for (const char of str) {
      if (char === '0') num++
    }
    return num
  }
  const dp = Array(m + 1).fill(0).map(_ => Array(n + 1).fill(0))
  for (const str of strs) {
    const cntZero = cnt(str)
    const cntOne = str.length - cntZero
    for (let j = m; j >= cntZero; j--) {
      for (let k = n; k >= cntOne; k--) {
        dp[j][k] = Math.max(dp[j][k], dp[j - cntZero][k - cntOne] + 1)
      }
    }
  }
  return dp[m][n]
}

时间复杂度：O(len*mn)；空间复杂度：O(mn)。

不同的子序列 ​

剑指 Offer II 097. 不同的子序列

问题转化为用str提供的石头填满容量为cap的背包，每个石头需要按顺序选择且只能选择一次，因此是一个0-1背包问题。

  • 状态定义：dp[i][j] = x，表示str中的前i个字符能够构成tar中前j个字符的种类数为x；
  • base case：dp[i][0] = 1；
  • 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i-1][j - 1]。
JavaScript
const numDistinct = (str, tar) => {
  const cap = tar.length
  const dp = Array(cap + 1).fill(0)
  dp[0] = 1
  for (const char of str) {
    for (let j = cap; j > 0; j--) {
      if (char === tar.charAt(j - 1)) {
        dp[j] += dp[j - 1]
      }
    }
  }
  return dp[cap]
}

时间复杂度：O(n*cap)；空间复杂度：O(cap)。

完全背包 ​

什么又是完全背包呢？

如果每件物品最多可以选取无限次，则问题称为完全背包问题。

  • 状态定义：dp[i][j] = x，表示前i件物品放入容量为j的背包时，可以获取的最大价值为x；
  • base case：根据情况分析；
  • 状态转移方程：dp[i][j] = Math.max(dp[i-1][j], dp[i][j-w[i]] + v[i])。

零钱兑换 ​

剑指 Offer II 103. 零钱兑换

  • 状态定义：dp[i][j] = x，表示从前i种硬币中组成金额j所需最少的硬币数量为x；
  • base case：dp[0][0] = 0；
  • 状态转移方程：dp[i][j] = Math.min(dp[i-1][j], dp[i][j - coins[i-1]] + 1)。
JavaScript
const coinChange = (coins, cap) => {
  const dp = Array(cap + 1).fill(Infinity)
  dp[0] = 0
  for (const coin of coins) {
    for (let j = coin; j <= cap; j++) {
      dp[j] = Math.min(dp[j], dp[j - coin] + 1)
    }
  }
  return dp[cap] === Infinity ? -1 : dp[cap]
}

时间复杂度：O(n*cap)；空间复杂度：O(cap)。

零钱兑换 II ​

518. 零钱兑换 II

  • 状态定义：dp[i][j] = x，表示从前i种硬币中凑出金额j的硬币组合数为x；
  • base case：dp[0][0] = 1，即空集合；
  • 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]]。
JavaScript
const change = (cap, coins) => {
  const dp = Array(cap + 1).fill(0)
  dp[0] = 1
  for (const coin of coins) {
    for (let j = coin; j <= cap; j++) {
      dp[j] += dp[j - coin]
    }
  }
  return dp[cap]
}

时间复杂度：O(n*cap)；空间复杂度：O(cap)。

组合总和 Ⅳ ​

377. 组合总和 Ⅳ

  • 状态定义：dp[i][j] = x，表示从前i个数能凑出和为j的组合数为x；
  • base case：dp[0][0] = 1；
  • 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j - nums[i-1]]。
JavaScript
const combinationSum4 = (nums, cap) => {
  const dp = Array(cap + 1).fill(0)
  dp[0] = 1
  for (let j = 1; j <= cap; j++) {
    for (const num of nums) {
      if (j >= num) {
        dp[j] += dp[j - num]
      }
    }
  }
  return dp[cap]
}

时间复杂度：O(n*cap)；空间复杂度：O(cap)。

完全平方数 ​

279. 完全平方数

  • 状态定义：dp[i][j] = x，从前i个完全平方数中凑出整数j所需最少的完全平方数的个数为x；
  • base case：dp[0][0] = 0，即不选任何完全平方数即可得到数值0；
  • 状态转移方程：dp[i][j] = Math.min(dp[i-1][j], dp[i][j - num*num] + 1)。
JavaScript
const numSquares = n => {
  const dp = Array(n + 1).fill(Infinity)
  dp[0] = 0
  const N = n * n
  for (let num = 1; num <= N; num++) {
    const I = num * num
    for (let j = I; j <= n; j++) {
      dp[j] = Math.min(dp[j], dp[j - I] + 1)
    }
  }
  return dp[n]
}

时间复杂度：O(n*Math.sqrt(n))；空间复杂度：O(n)。