TBH个人博客
背包做题笔记
tbghg
  2023-01-13 21:43:13   2023-01-13 21:43:13    7.3k 字  30 分钟

你的背包~🎵

前言

这个是刷代码随想录的做题笔记，分析部分大多是我自己的理解，代码我用go写的，现在回头再看一遍还是觉得代码随想录总结的很棒，强推一波！

背包概括

image

面试的话，其实掌握 01背包 完全背包，就够用了，leetcode上连多重背包的题目都没有

完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的。01背包是基础，需要重点掌握。

01背包

01背包初介绍

有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

先从暴力的角度来看，通过回溯实现暴力，每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是o(2^n)，这里的n表示物品数量。

所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化

入门例题

背包最大重量为4，物品为：

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

问背包能背的物品最大价值是多少？

分析

动规五部曲

  1. 确定dp数组以及下标的含义

对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少

0 1 2 3 4
物品0
物品1
物品2
  1. 确定递推公式

再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少

那么可以有两个方向推出来dp[i][j]：

  • 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同)
  • 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

  1. dp数组如何初始化

首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

0 1 2 3 4
物品0 0
物品1 0
物品2 0

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值

0 1 2 3 4
物品0 0 15 15 15 15
物品1 0
物品2 0

首先j=0(容量为0)这里是可以初始值不用管的，并且根据遍历顺序来说也是不用管，这个后面会看到

初始化的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
	weight := []int{1, 3, 4}
	value := []int{15, 20, 30}
	bigWeight := 4
	dp := make([][]int, len(weight))
	for i := 0; i < len(weight); i++ {
		// 因为容量包含0，所以要+1
		dp[i] = make([]int, bigWeight+1)
	}
	// 这里直接从weight[0]起步，前面的肯定是0
	for j := weight[0]; j <= bigWeight; j++ {
		dp[0][j] = value[0]
	}
	fmt.Println(dp)
}
// output:[[0 15 15 15 15] [0 0 0 0 0] [0 0 0 0 0]]
  1. 确定遍历顺序

01背包遍历顺序两种都行，但是先遍历物品更好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
// 遍历物品
for i := 1; i < len(weight); i++ {
    // 遍历容量
    for j := 0; j <= bagWeight; j++ {
        if j < weight[i] {
            dp[i][j] = dp[i-1][j]
        } else {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
        }
    }
}
fmt.Println(dp)
//output:[[0 15 15 15 15] [0 15 15 20 35] [0 15 15 20 35]]

滚动数组空间优化

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少

一维数组：dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]

动规五部曲

  1. 确定dp数组的定义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]

  1. dp数组的递推公式
1
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
  1. dp数组初始化

dp[0]=0，其他情况下可以通过dp[0]直接横着推过来

  1. 遍历顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
	weight := []int{1, 3, 4}
	value := []int{15, 20, 30}
	bagWeight := 4
	// 因为容量包含0，所以要+1
	dp := make([]int, bagWeight+1)
	// 遍历物品
	for i := 0; i < len(weight); i++ {
		// 遍历容量
		for j := bagWeight; j >= weight[i]; j-- {
			dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
		}
	}
	fmt.Println(dp)
}
//output:[0 15 15 20 35]

这块是重点，注意：必须先遍历物品再遍历背包；必须倒序遍历

先遍历物品再遍历背包：因为一维dp的写法，背包容量一定是要倒序遍历，如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品（举个例子自己走一遍就差不多理解了）

倒顺遍历：无法知道物品装了没装，容易装多次，倒着来的话本容量下前面的肯定没装该物品，因为还没遍历到

分割等和子集

题目链接

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

示例 1：

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

分析

[1,5,11,5]为例，和为22，相当于一个11的背包看看最多可以装多少个，如果小于11输出false，等于11输出true，一道简单的01背包问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func canPartition(nums []int) bool {
	var sum int
	for _, v := range nums {
		sum += v
	}
	if sum%2 != 0 {
		return false
	}
	sum /= 2
	dp := make([]int, sum+1)
	for i := 0; i < len(nums); i++ {
		for j := sum; j >= nums[i]; j-- {
			dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
		}
	}
	return dp[sum] == sum
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

最后一块石头的重量 II

题目链接

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

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0

示例 1：

1
2
3
4
5
6
7
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

1
2
输入：stones = [31,26,33,21,40]
输出：5

提示：

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

分析

乍一看一脸懵逼，仔细想想的话反正一个是加数一个是减数，分成两拨来碰，和上面那道题好像一样：一组数，分两拨，两拨之间差值如何最小，输出即可，那也就相当于一组数，sum/2为容量，看看最大是多少，最后输出sum/2-该数

但是需要考虑sum%2为1的情况，以sum=9为例，肯定有一波小于等于4，一波小于等于5，不管是哪一波，一个向中间聚拢，另一个也是，所以背包容量取哪个都没影响。我们可以直接向下取整，因为sum/2就是，并且容量小的话for层数也少。

因为背包容量算出来的是小于等于sum/2的，并且还有可能向下取整，所以最后结果为sum-dp[bagWeight] - dp[bagWeight]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func lastStoneWeightII(stones []int) int {
	var sum int
	for _, stone := range stones {
		sum += stone
	}
	bagWeight := sum / 2
	dp := make([]int, bagWeight+1)
	// 遍历物品
	for i := 0; i < len(stones); i++ {
		// 遍历容量
		for j := bagWeight; j >= stones[i]; j-- {
			dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
		}
	}
	return sum - dp[bagWeight]*2
}

目标和

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

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

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1"

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

1
2
输入：nums = [1], target = 1
输出：1

提示：

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

分析

这道题比较难想，但是有过这一次之后以后同类型的会好很多。

加号的分为一波，减号的分为一波，假设加法的总和为x，那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = target，x = (target + sum) / 2

此时问题就转化为，装满容量为x的背包，有几种方法

bagSize就是(target + sum) / 2 ，如果这个数不能整除，那就不可能凑不来方法，return 0即可

这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。本题则是装满有几种方法。其实这就是一个组合问题了

  1. 确定dp数组以及下标的含义

dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法

  1. 确定递推公式

dp[j]，j 为5

  • 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
  • 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
  • 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
  • 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
  • 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包

那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

所以求组合类问题的公式，都是类似这种：

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

这个公式在后面在讲解背包解决排列组合问题的时候还会用到！

  1. dp数组如何初始化

从0开始推，容量为0装满的方式有1种，这个是初始值，其他通过这个推过来。

从递推公式可以看出，在初始化的时候dp[0] 一定要初始化为1，因为dp[0]是在公式中一切递推结果的起源，如果dp[0]是0的话，递推结果将都是0。

  1. 确定遍历顺序

一维dp数组，先物品再容量

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func findTargetSumWays(nums []int, target int) int {
	sum := target
	for _, num := range nums {
		sum += num
	}
	if sum%2 == 1 {
		return 0
	}
	bagWeight := sum / 2
	// 这里需要判断bagWeight是否小于0
    // 例如 [100],-200 的输入
    if bagWeight < 0 {
        return 0
    }
	// dp[j] 表示：填满j这么大容积的包，有dp[j]种方法
	dp := make([]int, bagWeight+1)
	dp[0] = 1
	for i := 0; i < len(nums); i++ {
		for j := bagWeight; j >= nums[i]; j-- {
			dp[j] += dp[j-nums[i]]
		}
	}
	fmt.Println(dp)
	return dp[bagWeight]
}

一和零

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

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

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

示例 1：

1
2
3
4
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

1
2
3
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] 仅由 '0' 和 '1' 组成
  • 1 <= m, n <= 100

分析

这个题其实不难看出来是01背包问题但是有两个维度限制（经常见这类型的题），就像有的大招既扣蓝也扣血，这俩都算是背包的容量，所以我们for循环遍历需要三层了：物品、容量0、容量1（我们需要把dp[m][n]中，m、n取值的各种情况都填满！）

创建dp数组的时候再多创建一个维度即可，例如我们用滚动数组，一维数组即可解决，这里要变成二维

  1. 确定dp数组及下标的含义

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]

  1. 确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

然后我们在遍历的过程中，取dp[i][j]的最大值。

所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

此时大家可以回想一下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）

  1. dp数组如何初始化

根据含义dp[0][0]直接为0就行，滚动数组的话也不会覆盖掉什么的

  1. 确定遍历顺序

先遍历物品再遍历背包，从后往前遍历

代码

自我感觉注释写的挺清晰的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func findMaxForm(strs []string, m int, n int) int {
	// 滚动数组，所以 创建dp数组时无需考虑物品的容量
	// 因为是两个容量限制，所以是dp[m+1][n+1] (加一是因为含有0)
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
	}
	// 遍历物品
	for _, str := range strs {
		zeroNum,oneNum := 0,0
		for _, ch := range str {
			if ch == '0' {
				zeroNum++
			} else {
				oneNum++
			}
		}
		// 遍历容量
		for i := m; i >= zeroNum; i-- { // 遍历0的容量
			for j := n ; j >= oneNum; j-- { // 遍历1的容量
				dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)
			}
		}
	}
	return dp[m][n]
}

01背包总结

刚刚刷过的题目总结一下：

所以在代码随想录中所列举的题目，都是 0-1背包不同维度上的应用

【不得不说卡哥找的这些题都太典型了，每道题是一种类型，有些佩服】

完全背包

概述

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件

以例题为切入，背包最大重量为4，物品如下：

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

每件商品都有无限个，问背包能背的物品最大价值是多少？

回顾一下01背包的核心代码：

1
2
3
4
5
6
7
// 遍历物品
for i := 0; i < len(weight); i++ {
	// 遍历容量
	for j := bagWeight; j >= weight[i]; j-- {
		dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
	}
}

其中容量倒序遍历，为了保证每个物品仅被添加一次，而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

1
2
3
4
5
6
7
// 遍历物品
for i := 0; i < len(weight); i++ {
	// 遍历容量
	for j := weight[i]; j <= bagWeight; j-- {
		dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
	}
}

01背包中必须先遍历物品，再遍历容量，但完全背包中两种遍历方式都可以，因为dp[j]是根据 下标j之前所对应的dp[j]计算出来的，只要保证下标j之前的dp[j]都是经过计算的就可以了，而完全背包从前往后遍历，所以前面的数都是全的，咋遍历都没问题。

背包遍历顺序

  • 01背包：先物品后容量，容量倒序遍历
  • 完全背包：容量正序遍历，两种遍历方式都可以

但是！具体问题要具体分析，这里说的仅仅是纯背包问题的遍历顺序

顺便把例题做了吧，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func main() {
   weight := []int{1, 3, 4}
   value := []int{15, 20, 30}
   bagWeight := 4
   // 因为容量包含0，所以要+1
   dp := make([]int, bagWeight+1)
   // 遍历物品
   for i := 0; i < len(weight); i++ {
      // 遍历容量
      for j := weight[i]; j <= bagWeight; j++ {
         dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
      }
   }
   fmt.Println(dp)
}

零钱兑换 II

题目链接

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

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0

假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。

示例 1：

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

示例 2：

1
2
3
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

1
2
输入：amount = 10, coins = [10] 
输出：1

提示：

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

代码

和01背包中的那个题一样，组合问题：dp[j] += dp[j - nums[i]]，没啥好解释的

1
2
3
4
5
6
7
8
9
10
func change(amount int, coins []int) int {
	dp := make([]int, amount+1) //总金额为i时，有dp[i]种兑换方法
	dp[0] = 1
	for i := 0; i < len(coins); i++ {
		for j := coins[i]; j <= amount; j++ {
			dp[j] += dp[j-coins[i]]
		}
	}
	return dp[amount]
}

遍历顺序分析

但是注意，这里遍历顺序必须时先物品后容量！

因为纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！而本题要求凑成总和的组合数，元素之间明确要求没有顺序。所以纯完全背包是能凑成总和就行，不用管怎么凑的。本题是求凑出来的方案个数，且每个方案个数是为组合数。

外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

如果把两个for交换顺序，背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。此时dp[j]里算出来的就是排列数！

总结

  • 如果求组合数就是外层for循环遍历物品，内层for遍历背包
  • 如果求排列数就是外层for遍历背包，内层for循环遍历物品

组合总和 Ⅳ

题目链接

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

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

示例 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)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

1
2
输入：nums = [9], target = 3
输出：0

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

分析

标题写的时组合，实际上时排序，没啥好说的，for循环调换一下，换的时候注意需要把j-nums[i]<0的部刨掉

  • 如果求组合数就是外层for循环遍历物品，内层for遍历背包
  • 如果求排列数就是外层for遍历背包，内层for循环遍历物品

进阶：如果给定的数组中含有负数，则会导致出现无限长度的排列。
例如：有个-5，有个3。那我选3个-5，再选5个3，它们的和为0，那就抵消了，按照倍数往上加，像6个-5、10个3也是0，这样成倍增长下去，那就没完了

代码

1
2
3
4
5
6
7
8
9
10
11
12
func combinationSum4(nums []int, target int) int {
   dp := make([]int, target+1)
   dp[0] = 1
   for j := 0; j <= target; j++ {
      for i := 0; i < len(nums); i++ {
         if j-nums[i] >= 0 { // 这个判断得单独处理
            dp[j] += dp[j-nums[i]]
         }
      }
   }
   return dp[target]
}

爬楼梯进阶版

假设你正在爬楼梯。需要 n 阶你才能到达楼顶，你每次可以上1至m个台阶，n、m均为输入。你有多少种不同的方法可以爬到楼顶呢？

分析

  • 每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶——完全背包
  • 跳到楼顶有几种方法——排序问题

从而确定遍历顺序：

  • 完全背包：容量正序遍历
  • 排序问题：先容量再物品

dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。递推公式：dp[i] += dp[i - j]。初始化：dp[0]=0

代码

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

零钱兑换

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

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

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

示例 1：

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

示例 2：

1
2
输入：coins = [2], amount = 3
输出：-1

示例 3：

1
2
输入：coins = [1], amount = 0
输出：0

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

分析

  • 确定dp数组：凑足总额为j所需钱币的最少个数为dp[j]
  • 确定递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j])
  • dp数组如何初始化[值得注意]：非0的元素都是应该是最大值，dp[0]=0
  • 遍历顺序：求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1) // 总金额为i时，最少硬币数为dp[i]
	// dp[j] = min(dp[j],dp[j-coins[i]]+1)
	for i := 1; i <= amount; i++ {
		dp[i] = math.MaxInt32
	}
	for i := 0; i <= len(coins); i++ {
		for j := coins[i]; j <= amount; j++ {
			dp[j] = min(dp[j], dp[j-coins[i]]+1)
		}
	}
	return dp[amount]
}

完全平方数

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= n <= 10^4

分析

题目翻译：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品

  • 完全背包
  • 遍历顺序没要求

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func numSquares(n int) int {
	dp := make([]int, n+1) // j需要的最少平方数个数
	for i := 1; i <= n; i++ {
		dp[i] = math.MaxInt32
	}
	m := int(math.Pow(float64(n), 0.5))
	// 遍历物品
	for i := 0; i <= m; i++ {
		// 遍历容量
		for j := i * i; j <= n; j++ {
			dp[j] = min(dp[j], dp[j-i*i]+1)
		}
	}
	return dp[n]
}

多重背包

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

多重背包和01背包是非常像的，每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

例如：

背包最大重量为10。

物品为：

重量 价值 数量
物品0 1 15 2
物品1 3 20 3
物品2 4 30 2

问背包能背的物品最大价值是多少？

和如下情况有区别么？

重量 价值 数量
物品0 1 15 1
物品0 1 15 1
物品1 3 20 1
物品1 3 20 1
物品1 3 20 1
物品2 4 30 1
物品2 4 30 1

毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。

所以可以直接把它看成01背包来做。当然另一种实现方式，就是把每种商品遍历的个数放在01背包里面在遍历一遍。即01背包里面在加一个for循环遍历一个每种商品的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 多重背包可以化解为 01 背包
func multiplePack(weight, value, nums []int, bagWeight int) int {
    
	for i := 0; i < len(nums); i++ {
		for nums[i] > 1 {
			weight = append(weight, weight[i])
			value = append(value, value[i])
			nums[i]--
		}
	}

	res := make([]int, bagWeight+1)
	for i := 0; i < len(weight); i++ {
		for j := bagWeight; j >= weight[i]; j-- {
			res[j] = getMax(res[j], res[j-weight[i]]+value[i])
		}
	}

	return res[bagWeight]
}

背包总结

01背包：

  • 物品只能用一次
  • 二维数组时，遍历顺序均可
  • 一维数组只能先物品后容量，容量倒序遍历

完全背包：

  • 物品可用无限次
  • 容量正序遍历（保证无限次）
  • 一维数组遍历顺序均可，常见特例如下：
    • 组合数：先遍历物品，再遍历容量(背包)
    • 排序数：先遍历容量(背包)，再遍历物品

多重背包：转换成01背包来做

组合、排序问题递推通常公式为：dp[i] += dp[i - j]，初始化dp[0]=0

OK，你已经掌握01背包、完全背包、多重背包了，快去solo面试官吧！

 评论
评论插件加载失败
正在加载评论插件
  1. 1. 前言
  2. 2. 背包概括
  3. 3. 01背包
    1. 3.1. 01背包初介绍
    2. 3.2. 入门例题
      1. 3.2.1. 分析
      2. 3.2.2. 滚动数组空间优化
    3. 3.3. 分割等和子集
      1. 3.3.1. 分析
      2. 3.3.2. 代码
    4. 3.4. 最后一块石头的重量 II
      1. 3.4.1. 分析
      2. 3.4.2. 代码
    5. 3.5. 目标和
      1. 3.5.1. 分析
      2. 3.5.2. 代码
    6. 3.6. 一和零
      1. 3.6.1. 分析
      2. 3.6.2. 代码
    7. 3.7. 01背包总结
  4. 4. 完全背包
    1. 4.1. 概述
    2. 4.2. 零钱兑换 II
      1. 4.2.1. 代码
      2. 4.2.2. 遍历顺序分析
    3. 4.3. 组合总和 Ⅳ
      1. 4.3.1. 分析
      2. 4.3.2. 代码
    4. 4.4. 爬楼梯进阶版
      1. 4.4.1. 分析
      2. 4.4.2. 代码
    5. 4.5. 零钱兑换
      1. 4.5.1. 分析
      2. 4.5.2. 代码
    6. 4.6. 完全平方数
      1. 4.6.1. 分析
      2. 4.6.2. 代码
  5. 5. 多重背包
  6. 6. 背包总结
  1. 1. 前言
  2. 2. 背包概括
  3. 3. 01背包
    1. 3.1. 01背包初介绍
    2. 3.2. 入门例题
      1. 3.2.1. 分析
      2. 3.2.2. 滚动数组空间优化
    3. 3.3. 分割等和子集
      1. 3.3.1. 分析
      2. 3.3.2. 代码
    4. 3.4. 最后一块石头的重量 II
      1. 3.4.1. 分析
      2. 3.4.2. 代码
    5. 3.5. 目标和
      1. 3.5.1. 分析
      2. 3.5.2. 代码
    6. 3.6. 一和零
      1. 3.6.1. 分析
      2. 3.6.2. 代码
    7. 3.7. 01背包总结
  4. 4. 完全背包
    1. 4.1. 概述
    2. 4.2. 零钱兑换 II
      1. 4.2.1. 代码
      2. 4.2.2. 遍历顺序分析
    3. 4.3. 组合总和 Ⅳ
      1. 4.3.1. 分析
      2. 4.3.2. 代码
    4. 4.4. 爬楼梯进阶版
      1. 4.4.1. 分析
      2. 4.4.2. 代码
    5. 4.5. 零钱兑换
      1. 4.5.1. 分析
      2. 4.5.2. 代码
    6. 4.6. 完全平方数
      1. 4.6.1. 分析
      2. 4.6.2. 代码
  5. 5. 多重背包
  6. 6. 背包总结