几道完全背包问题

零钱兑换

问题描述

leetcode 518

示例

1
2
3
4
5
6
7
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

问题分析

本笔记不再考虑二维 $dp$ 数组情况，直接使用一维 $dp$ 数组，下面几道题目也一样。

本题中要凑的总金额就是背包的最大重量，并且必须要把背包填满。

要求的是能填满背包的方法数（硬币的选择方式组合数）。

$dp$​ 数组定义

$dp[j]$​ 代表为填满容量为 $j$​ 背包有 $dp[j]$​ 种方式。

递推公式

那么对于背包容量 $j$，在 $0$ ~ $i$ 选取物品 $coins[i]$，如果此时背包恰好还剩余 $j - coins[i]$ 的容量，那么再选一个 $coins[i]$ 就将背包填满了。此时填满 $j$ 容量的方法数和填满 $j - coins[i]$ 的方法数是一样的（因为从 $j - coins[i]$ 再选一个 $coins[i]$​​ 就填满了，只有这一种情况）。

而 $dp[j]$ 的最终结果，就是对于每一个物品的选择情况求和。

初始化方式

在纯完全背包中，初始化 $dp[0] = 0$（容量为 $0$ 的背包能容纳的物品也是 $0$）。

但是在当前题目中是不可以的，因为每个 $dp[j]$ 都是通过前面遍历过的位置推导而来的，那么如果第一个位置 $dp[0] = 0$，那么所以 $dp[j]$ 都将是 $0$。

所以在本题题目中应该将 $dp[j]$ 设置为 $1$（填满容量为 $0$ 的背包的方法数为 $1$ 种，就是不选择物品）。

遍历顺序

与 $01$​ 背包不同，在完全背包中，遍历方式是有讲究的。

第一种方式：先遍历物品，再遍历背包。在这种方式中，每个物品的出现是有先后顺序的（也就是说答案是组合数）。

1
2
3
4
5
6
7
8
9
10
11
//遍历物品
for i := 0; i < len(coins); i++ {
    //遍历背包最大容量，dp[0] 已经初始化，从 dp[1] 开始
    for j := 1; j <= amount; j++ {
        //只有背包容量大于或等于当前硬币重量时，能能选择
        if j >= coins[i] {
            //累加所有情况
            dp[j] += dp[j - coins[i]]
      }
  }
}

第二种方式：先遍历背包，再遍历物品。在这种方式中，对于每个背包，每一个物品都可以先出现（也就是说答案是排列数）。

1
2
3
4
5
6
7
8
9
10
11
//遍历背包最大容量，dp[0] 已经初始化，从 dp[1] 开始
for j := 1; j <= amount; j++ {
    //遍历物品
    for i := 0; i < len(coins); i++ {
        //只有背包容量大于或等于当前硬币重量时，能能选择
        if j >= coins[i] {
            //累加所有情况
            dp[j] += dp[j - coins[i]]
      }
  }
}

举例推导

以实例 $coins = [1, 2, 5]$​ 为例展示推导过程：

（1）初始化后：

（2）对于 $coins[0]$​​​​​ 遍历背包容量：

  • 对于容量 $1$​ 的背包，选 $1$ 个 $1$​
  • 对于容量 $2$​ 的背包，选 $2$​ 个 $1$​​
  • …

所以每一个都是一种方法。

（3）对于 $coins[1]$​​​​ 遍历背包容量：$dp[1]$ 不满足 $j >= coins[i]$​​​，跳过。

  • 对于容量 $2$ 的背包
    • $1 + 1$
    • $2$​
  • 对于容量 $3$​​ 的背包
    • $1 + 1 + 1$​
    • $1 + 2$​

  • 对于容量 $4$​​​ 的背包

    • $1 + 1 + 1 + 1$​​
    • $1 + 1 + 2$​​
    • $2 + 2$

  • 对于容量 $5$​​ 的背包

    • $1 + 1 + 1 + 1 + 1$​
    • $1 + 1 + 1 + 2 $​
    • $1 + 2 + 2$​

（4）对于 $coins[2]$​ 遍历操作同理，略。

golang 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var (
  coins = []int{1, 2, 5}
)

func change(amount int, coins []int) int {
  dp := make([]int, amount + 1)
  dp[0] = 1
  for i := 0; i < len(coins); i++ {
    for j := 1; j <= amount; j++ {
      if j >= coins[i] {
        dp[j] += dp[j - coins[i]]
      }
    }
  }
  return dp[amount]
}

复杂度分析

时间复杂度为 $O(mn)$​，其中 $m$​ 是需要凑满的目标数 $amount$​，$n$​ 是硬币个数。

空间复杂度是 $O(m)$。

组合总和 IV

问题描述

leetcode 377

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

问题分析

$dp$ 数组定义

$dp[j]$​​ 代表填满容量 $j$ 的背包的元素组合数。

递推公式

对于容量 $j$ 的背包、在选择物品 $nums[i]$​​ 时，装满背包的组合数，就是装满容量 $j - nums[i]$​​​ 的背包的组合数。

那么对于所以物品 $nums$​，装满容量 $j$ 的背包的组合总数，就是把上述针对每个物品的组合数求总和。

$dp$ 数组初始化

从递推公式中可以看出，结果是累加求得的，那么 $dp$​ 数组的第一个位置就必须要初始化。

要装满容量为 $0$ 的背包，只能是什么都选择，也就是空集合，只有这一种方式。

遍历顺序

因为是本题求的是所以可能的组合数，也就是求排列。

在上一道题目中已经分析，遍历顺序就是先遍历背包（保证选择物品是无序的），再遍历物品。

举例推导

以示例为例，推导一下过程

初始化

物品 $1$​​，遍历所以物品

背包 $2$​​​，遍历所有物品

背包 $3$​​，遍历所有物品

背包 $4$​​，遍历所有物品

golang 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
func combinationSum4(nums []int, target int) int {
    dp := make([]int, target + 1)
    dp[0] = 1 //填满0容量的背包，有一种组合，就是空[]
    //本题求组合，所以遍历顺序必须先背包后物品
    for j := 0; j <= target; j++ {
        for i := 0; i < len(nums); i++ {
            if j >= nums[i] {
                dp[j] += dp[j - nums[i]]
            }
        }
    }
    return dp[target]
}

复杂度分析

时间复杂度为 $O(mn)$，其中 $m$ 是需要凑满的目标数 $target$，$n$ 是硬币个数。

空间复杂度是 $O(m)$。

爬楼梯

问题描述

leetcode 70

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

1
2
3
4
5
6
7
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

递归解法

爬到第 $0$​ 阶台阶有 $1$ 种方法，就是不爬。

爬到第 $1$​ 阶台阶，只能选择走 $1$ 阶，有 $1$​ 种方法。

爬到第 $2$​ 阶台阶，可以选择每次走 $1$​ 阶，也可以选择一次走 $2$ 阶，有 $2$​​ 种方法。

爬到第 $3$​​ 阶台阶，可以选择从第 $2$​ 阶走 $1$​ 阶到达，也可以选择从第 $1$​ 阶一次走 $2$​ 阶到达，有 $f(3 - 1) + f(3 - 2)$ 种方法。

这是一道很简单的题目，实际就是求一下斐波那契数列。

1
2
3
4
5
6
func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    return climbStairs(n - 2) + climbStairs(n - 1)
}

动态规划

递归解法会有大量的重复计算，例如计算 $f(3 - 2)$​ 的内部已经递归计算了 $f(3 - 1)$​。

可以通过一个数组存储前一个计算的值，正向推导。

1
2
3
4
5
6
7
8
9
10
11
func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    dp := make([]int, n + 1)
    dp[0], dp[1] = 1, 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

但是实际最终答案需要的只是 $dp$ 数组最后一个元素，实际使用长度为 $2$​ 的 $dp$ 数组就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    dp := []int{1, 2}
    for i := 3; i <= n; i++ {
        tmp := dp[0] + dp[1]
        dp[0] = dp[1]
        dp[1] = tmp
    }
    return dp[1]
}

问题扩展

将问题改为每一次可以爬 $1$​ 、 $2$​ 、 $3$​​​ 、… 阶台阶，爬到第 $n$​ 阶台阶有多少种方法？

分析

实际上可以理解为，现在有一组物品：$[1, 2, 3, …, n]$，有一个背包最大容量为 $n$​​，要装满这个背包有多少种选择方式。

物品可以无限次重复选择，所以这就是一道完全背包的问题。

与上面的题就是一样的解法了，重点同样在于求的是排列，所以要先遍历背包。

零钱兑换 II

问题描述

leetcode 322

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

问题分析

$dp$ 数组定义

$dp[j]$ 代表装满容量为 $j$ 的背包所使用的最少的硬币数量。

递推公式

那么对于容量 $j$​ 的背包，在选择硬币 $coins[i]$​ 后刚好装满，那么此时使用的硬币数量就是 $dp[j - coins[i]] + 1$​。

那么对于所有的硬币 $coins$​ ，$dp[j]$ 就要取一个最小的值。

初始化

这里的初始化非常关键，前几道题目的在初始化时只需要考虑第一个元素就可以了。但是本题，递推公式需要计算最小值，那么如果还是初始化为 $0$，那么在状态转移过程中就会都取了 $0$ 值，达不到推导的目的。

所以 $dp[0] = 0$，装满容量为 $0$ 的背包，需要最少 $0$ 枚硬币。

其他位置都初始化为 $MaxInt$​。

遍历顺序

本题求的是最小硬币个数，所以不关心排列还是组合，遍历顺序是无所谓的。

golang 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func coinChange(coins []int, amount int) int {
  //背包
  dp := make([]int, amount + 1)
  //初始化
  for j := 1; j <= amount; j++ {
    dp[j] = math.MaxInt32
  }
  //先遍历物品，再遍历背包（本题不是求排列组合，所以顺序是可以颠倒的）
  for i := 0; i < len(coins); i++ {
    for j := 1; j <= amount; j++ {
      if j >= coins[i] {
        dp[j] = min(dp[j], dp[j - coins[i]] + 1)
      }
      // fmt.Println(dp)
    }
  }
    if dp[amount] >= math.MaxInt32 {
        return -1
    }
  return dp[amount]
}

复杂度分析

时间复杂度为 $O(mn)$，其中 $m$ 是需要凑满的金额总数，$n$ 是硬币个数。

空间复杂度是 $O(m)$。

完全平方数

问题描述

leetcode 279

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

1
2
3
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

问题分析

整体跟前几道题目大同小异，不再详细记录了。

只要理解了题目意思就简单了，物品就是完全平方数列表，那么有哪些完全平方数呢

之前的题目里，物品列表是题目给定的，而本题题目列表是根据参数动态变化的，需要自己计算。

对于背包容量 $n$​，最小的有意义的完全平方数就是 $n$​​，所有大于这个数值的完全平方数都无法使用，因为超过了背包的最大容量。

所以物品列表实际就是 $1^2$​​ ~ $(\sqrt{n})^2$​​​​，只需要在遍历物品时从 $1$ 开始，到 $\sqrt{n}$ 截止，然后自行计算当前遍历到的完全平方数即可。

$dp$ 数组定义

$dp[j]$ 代表装满容量为 $j$​ 的背包所使用的最少的完全平方数的数量。

初始化

跟上一道题类似。$dp[0] = 0$，其他为 $MaxInt$​。

遍历顺序

与上一题一样，同样不关心组合还是排列，所以遍历顺序随意。

golang 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func numSquares(n int) int {
  dp := make([]int, n + 1)
  //初始化
  for i := 1; i <= n; i++ {
    dp[i] = math.MaxInt32
  }
  //物品就是从1开始的每个数的平方，并控制物品列表最大到 i*i
  for i := 1; i*i <= n; i++ {
        //遍历背包
    for j := 1; j <= n; j++ {
      if j >= (i * i) { //物品的价值就是 i*i，之前的物品价值都是固定的，本题需要自己计算
        dp[j] = min(dp[j], dp[j - (i * i)] + 1)
      }
    }
  }
  return dp[n]
}

复杂度分析

外层循环最大要遍历 $n$，内层循环最大遍历 $\sqrt{n}$​，所以时间复杂度为 $O(n\sqrt{n})$。

空间复杂度为 $O(n)$。

单词拆分

问题描述

leetcode 139

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

问题分析

这道题目与前几道题目的差别就有些大了，但实际上也是一道完全背包问题。

物品列表就是 $wordDict$​，背包就是字符串 $s$​，把 $s$​ 拆分为一个或多个 $wordDict$​​ 中的单词反，这一操作反过来理解就是从物品列表中任意选择单词，最终能够拼成字符串 $s$​（也就是把背包装满），单词可以重复选择，这就是一个完全背包问题。

之前的题目物品列表都是固定的，操作过程是：选择物品，放入背包。

而本题中，这个操作程就多了一个前置动作：先截取子字符串，然后判断是否存在这个物品，存在的话才能放入背包（当然也可以预先生成一个包含所有的子串的容器，然后逐个判断）。

$dp$ 数组定义

背包就是字符串 $s$，边界条件就是空字符串，所以背包就是字符串 $s$ 的长度 $+1$​。

1
dp := make([]bool, len(s) + 1)

对于 $dp[j]$ ，指字符串长度为 $j$ 。如果 $dp[j]$ 为 $true$，表示 $s[0:j+1]$ 可以拆分为一个或多个在 $wordDict$ 中出现的单词。

递推公式

对于每个 $dp[j]$​，从 $i \in [0, j - 1]$​ 遍历字符串 $s$​，当 $dp[i]=true$​，并且 $s[i:j]$​ 在 $wordDict$​ 中时，$dp[j] = true$​​。

之前的题目中，在选择物品时，对于物品 $nums[i]$，只需要考虑选或不选，并通过 $dp[j - nums[i]]$ 就可以定位到上一个物品的选择情况。

但是在本题中，对于背包容量 $j$ 和物品遍历 $i$​，$i$ 并不是一个唯一的物品，而是从 $0$ 到 $i$ 可能出现的所有子串。

例如在求 $dp[3]$​​​ 时，如果：

  • $dp[2] = true$​，且 $wordDict$​​ 中包含 $s[2:3]$​
  • $dp[1] = true$​​，且 $wordDict$​​ 中包含 $s[1:3]$​​​
  • $wordDict$ 中包含 $s[0:3]$

三种情况满足一种，就说明 $s[0:j]$ 这个子串是可以被拆分为一个或多个 $wordDict$​ 中的单词的。

初始化

因为 $dp[j]$ 的推导依赖前面的推导结果，所以 $dp[0]$ 必须初始化为 $true$，其他位置为 $false$​。

遍历顺序

本题不用考虑排列还是组合，所以遍历顺序就是无所谓的。

但是需要注意的是，如果先遍历物品的话，那么此时是没有参数遍历帮助我们截取子串的，那么就需要像如上分析一样，预先生成一个包含所有子串的容器当作物品列表，然后在后续的遍历过程中再判断子串是否在 $wordDict$ 中。

所以本题先遍历背包容量比较容易一些。

举例推导

以示例为例，定义背包

初始化

容量 $1$​，能截取的子串是 l，$wordDict$​ 中不存在。

容量 $2$​​，能截取出的子串依次是 le、e，$wordDict$​​​​ 中都不存在。

容量 $3$，能截取出的子串依次是 lee、ee、e，$wordDict$ 中都不存在。

容量 $4$，能截取出的子串依次是 leet、eet、et、t，$wordDict$​ 中存在 leet，更新 $dp$ 数组：

容量 $5$，能截取出的子串依次是 leetc、eetc、etc、tc、c，$wordDict$ 中都不存在。

容量 $6$​，能截取出的子串依次是 leetco、eetco、etco、tco、co，$wordDict$​ 中都不存在。

容量 $7$​，能截取出的子串依次是 leetcod、eetcod、etcod、tcod、cod，$wordDict$​​​ 中都不存在。

容量 $8$​，能截取出的子串依次是 leetcode、eetcode、etcode、tcode、code，$wordDict$​​ 中存在 code，更新 $dp$ 数组：

golang 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func wordBreak(s string, wordDict []string) bool {
    m := make(map[string]bool)
    for _, v := range wordDict {
        m[v] = true
    }
    //背包
    dp := make([]bool, len(s) + 1)
    //初始化
  dp[0] = true
    //先遍历背包
  for j := 1; j <= len(s); j++ {
        //截取子字符串，尝试去搜索是否存在对应的物品
    for i := 0; i < j; i++ {
            //背包容量 j 对应的就是 s 的第几个字符
      if dp[i] && m[s[i:j]] {
        dp[j] = true
                break
      }
    }
    // fmt.Println(dp)
  }
  return dp[len(s)]
}

复杂度分析

首先需要遍历字符串长度 $n$，然后对于每个节点又最多有 $n$ 个子串切割，所以时间复杂度为 $O(n)$。

空间复杂度为 $O(n$)。

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

曾经是个修理工，<br>现在是一枚码农。<br>路漫漫其修远兮，<br>吾将上下而求索。<br>