动态规划-2
01背包问题
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
暴力的解法:把所有的情况全部试一遍,时间复杂度是$o(2^n)$
使用动态规划的方法:
- 二维
dp
算法:
确定
dp
数据及其下标的含义。dp[i][j]
表示从下标为[0-i]
的物品里任意取,放进容量为j
的背包,价值总和最大是多少。确定递推公式
再回顾一下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])
;- 不放物品i:由
dp
数组初始化:状态转移方程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的物品的时候,各个容量的背包所能存放的最大价值。那么很明显当
j < weight[0]
的时候,dp[0][j]
应该是 0,因为背包容量比编号0的物品重量还小。当
j >= weight[0]
时,dp[0][j]
应该是value[0]
,因为背包容量放足够放编号0物品。遍历顺序:先遍历物品,再遍历背包重量更好理解。
- 二维
1 |
|
一维dp
数组:
- 在一维dp数组中,dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]。
- 递推公式:
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
- 取价值最大的数,如果题目价值都是正整数,就都初始化为0就可以。
- 一维dp数组遍历顺序,从大到小。倒序遍历是为了保证物品i只被放入一次!。但如果一旦正序遍历了,那么物品0就会被重复加入多次!
- 进行模拟验证。
1 | void test_1_wei_bag_problem() { |
给你一个 只包含正整数 的 非空 数组 nums
。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
1 | 输入:nums = [1,5,11,5] |
- 背包的体积为sum / 2
- 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
- 背包如果正好装满,说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
动规五部曲:
dp[j]
表示背包总容量是j
,最大可以凑成j的子集总和为dp[j]
。- 01背包的递推公式为:
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
- 如果题目给的价值都是正整数那么非0下标都初始化为0就可以了,如果题目给的价值有负数,那么非0下标就要初始化为负无穷。
- 如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!
- 举例推导dp数组
1 | class Solution { |
1049. 最后一块石头的重量 II - 力扣(LeetCode)
有一堆石头,用整数数组 stones
表示。其中 stones[i]
表示第 i 块石头的重量。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x
和 y
,且 x <= y
。那么粉碎的可能结果如下:
如果 x == y
,那么两块石头都会被完全粉碎;
如果 x != y
,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0。
示例 1:
1 | 输入:stones = [2,7,4,1,8,1] |
本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。
动态规划五部曲:
- dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背dp[j]这么重的石头。
- 递推公式:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
- dp数组初始化:
vector<int> dp(15001, 0);
- 如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!
- 举例推导dp数组
1 | class Solution { |
给你一个整数数组 nums
和一个整数 target
。
向数组中的每个整数前添加 '+'
或 '-'
,然后串联起所有整数,可以构造一个 表达式 :
例如,nums = [2, 1]
,可以在 2
之前添加 '+'
,在 1
之前添加 '-'
,然后串联起来得到表达式 "+2-1"
。
返回可以通过上述方法构造的、运算结果等于 target
的不同 表达式 的数目。
1 | 输入:nums = [1,1,1,1,1], target = 3 |
动规五步曲:
- 确定dp数组以及下标的含义,dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法
- 确定递推公式:dp[j] += dp[j - nums[i]] 求组合问题都是这个公式。
- dp数组如何初始化:从递归公式可以看出,在初始化的时候dp[0] 一定要初始化为1,因为dp[0]是在公式中一切递推结果的起源,如果dp[0]是0的话,递归结果将都是0。
- 遍历顺序:我们讲过对于01背包问题一维dp的遍历,nums放在外循环,target在内循环,且内循环倒序。
- 举例推导dp数组。
1 | //时间复杂度:O(n × m),n为正数个数,m为背包容量 |
给你一个二进制字符串数组 strs
和两个整数 m
和 n
。
请你找出并返回 strs
的最大子集的长度,该子集中 最多 有 m
个 0
和 n
个 1
。
如果 x
的所有元素也是 y
的元素,集合 x
是集合 y
的 子集 。
1 | 输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 |
动规五部曲:
- 确定dp数组(dp table)以及下标的含义:
dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]
。 - 递推公式:类比0,1背包的递推公式:
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); dp[i][j]
就可以是dp[i - zeroNum][j - oneNum] + 1。
- 因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。
- 物品就是strs里的字符串,背包容量就是题目描述中的m和n。
- 举例推导dp数组
1 | class Solution { |
完全背包概述
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。
与01背包的区别就是每种物品有无限件。
之前提过01背包的物品只能添加一次,因此内层背包容量遍历时只能从从后向前遍历。而多重背包由于每个物品有多个,因此遍历时内层应该从前向后遍历。
多重背包先遍历背包或者先遍历物品均可,不会影响dp数组。
测试代码:
1 | // 先遍历物品,在遍历背包 |
给你一个整数数组 coins
表示不同面额的硬币,另给一个整数 amount
表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0
。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1:
1 | 输入:amount = 5, coins = [1, 2, 5] |
递归五部曲:
- dp含义:dp[j]表示凑成总金额为j的方式为dp[j]种。
- 递推公式:dp[j] = dp[j] + dp[j - coin[i]];
- 初始化:dp[0] = 1; 其他的dp[j] = 0;
- 确定遍历顺序:本题求的是组合数,因此先遍历物品,再遍历背包;如果求排列数,就是先遍历背包,再遍历物品。
- 举例推导dp数组。
1 | class Solution { |
给你一个由 不同 整数组成的数组 nums
,和一个目标整数 target
。请你从 nums
中找出并返回总和为 target
的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
1 | 输入:nums = [1,2,3], target = 4 |
动规五部曲:
- dp[j]表示组成目标整数
j
共有dp[j]种方法。 - 递推公式:dp[j] = dp[j] + dp[j - nums[i]]
- 初始化,dp[0] = 1, 其余均为0;
- 遍历顺序,多重背包的组合问题,从前到后,先遍历背包容量,再遍历物品。
- 检查dp数组是否正确。
1 | class Solution { |
总结:
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
给你一个整数数组 coins
,表示不同面额的硬币;以及一个整数 amount
,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1
。
你可以认为每种硬币的数量是无限的。
示例 1:
1 | 输入:coins = [1, 2, 5], amount = 11 |
递归五部曲
dp[j]
数组的含义,凑成总金额j
需要的最小的金币的数量是dp[j]
。- 递归公式:dp[j]只能从dp[j - coin[i]]中来,因此dp[j] = min(dp[j], dp[j - coin[i]] + 1)
- 初始化:dp[0]应该为0,其余的应该为INT_MAX
- 遍历顺序,多重背包,非排列或组合的遍历顺序。
- 验证dp数组
1 | class Solution { |
给你一个整数 n
,返回 和为 n
的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1
、4
、9
和 16
都是完全平方数,而 3
和 11
不是。
示例 1:
1 | 输入:n = 12 |
动规五部曲:
- dp[j] 数组表示组成和 为j 最少需要dp[j] 个完全平方数。n相当于背包容量,完全平方数相当于物品重量。
- dp数组递推公式:dp[j] = min(dp[j], dp[j - i * i] + 1);
- 初始化:dp[0] = 0; 其余的都为INT_MAX;
- 递归顺序,多重背包的递归顺序。
- 模拟dp数组。
1 | class Solution { |
给你一个字符串 s
和一个字符串列表 wordDict
作为字典。请你判断是否可以利用字典中出现的单词拼接出 s
。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1:
1 | 输入: s = "leetcode", wordDict = ["leet", "code"] |
动规五部曲:
- dp数组含义字符串长度为
i
,如果dp[i]为true,说明可以拆分一个或多个在字典中出现的单词。 - 递推公式:如果确定dp[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dp[i]一定是true。(j < i )。
- 初始化:dp[0]一定要为true
- 遍历顺序:完全背包的顺序,不是排列也不是组合,都可以
1 | class Solution { |