专项突破——背包问题
引用：
详细细节：咱就把01背包问题讲个通透！ - 力扣（LeetCode），动态规划：关于完全背包，你该了解这些！ - 力扣（LeetCode）
其他总结：【背包问题】 - 力扣（LeetCode）基础背包问题总结 - 力扣（LeetCode）
正文：
二维：
dp[i][j]的含义： 从下标为0，i-1的物品里任意取，放进容量为j的背包，最大价值。
一维：
dp[i]，目前，背包重量为i时，最大的价值。
一些模板请参考引用。
总结：
| 二维 | 一维 | |||
|---|---|---|---|---|
| 遍历顺序 | 正逆序 | 遍历顺序 | 正逆序 | |
| 0-1背包 | 都行 | 都正 | 先物品，后目标 | 目标逆序 |
| 完全背包 | 组合数：都行 排列数：先目标，后物品， 且dp状态转移方程会变 （推荐用一维） | 都正 | 组合数：先物品，后目标 排列数：先目标，后物品 | 都正 |
注意点：
二维：因为dp状态转移方程不同（大概率是if-else), 所以写循环的时候要判断一下。
一维：因为dp状态转移方程不同（大概率是if)，所以写循环的时候不要判断，直接写在内循环的for结构里。
例题：
0-1背包问题：
1049. 最后一块石头的重量 II - 力扣（Leetcode）
解答：
二维解法：
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
"""
题目相当于：分成两个阵营，相互粉碎，求最小值
变成0-1背包问题：从中拿石头，求能重量和最接近sum / 2的结果
"""
Sum = sum(stones)
dp = [[False] * (Sum + 1) for _ in range(len(stones) + 1)]
for i in range(len(stones) + 1):
# True表示能取到
dp[i][0] = True
# 二维数组，遍历顺序无所谓
for j in range(0, Sum + 1):
for i in range(1, len(stones) + 1):
if j - stones[i-1] >= 0:
dp[i][j] = dp[i-1][j - stones[i-1]] or dp[i-1][j]
else:
dp[i][j] = dp[i-1][j]
res = Sum
for i in range(Sum + 1):
if dp[-1][i]:
res = min(res, abs(Sum-2*i))
return res一维解法：
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
"""
题目相当于：分成两个阵营，相互粉碎，求最小值
变成0-1背包问题：从中拿石头，求能重量和最接近sum / 2的结果
"""
Sum = sum(stones)
dp = [False] * (Sum+1)
dp[0] = True
# 一维，先物品后背包，背包逆序
for i in range(1, len(stones) + 1):
for j in range(Sum, stones[i-1]-1, -1):
if dp[j-stones[i-1]] != 0:
dp[j] = True
res = Sum
for i in range(len(dp)):
if dp[i]:
res = min(res, abs(Sum-2*i))
return res**
解答：
二维解法
class Solution:
def canPartition(self, nums: List[int]) -> bool:
# 0-1 背包问题
# 先判断
nums_sum = sum(nums)
if nums_sum % 2 == 1:
return False
n = len(nums)
target = nums_sum // 2
# dp[i][j]表示前i - 1个数能否取到j - 1
dp = [[False] * (target + 1) for _ in range(len(nums) + 1)]
for i in range(len(nums) + 1):
dp[i][0] = True
# 二维0-1背包物品目标遍历顺序随便
for i in range(1, len(nums) + 1):
for j in range(1, target + 1):
if j >= nums[i-1]:
dp[i][j] = dp[i-1][j] or dp[i-1][j - nums[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[-1][-1]
一维解法：
class Solution: def canPartition(self, nums: List[int]) -> bool: # 0-1 背包问题 # 先判断 nums_sum = sum(nums) if nums_sum % 2 == 1: return False n = len(nums) target = nums_sum // 2 # dp[i]表示能否取到i - 1 dp = [False] * (target + 1) dp[0] = True # 一维0-1背包，先物品，后目标，目标逆序 for num in nums: for j in range(target, num - 1, -1): dp[j] = dp[j] or dp[j - num] return dp[-1]
完全背包问题：
解答：
二维数组解法：
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
# 完全背包问题，组合数
dp = [[0] * (amount + 1) for _ in range(len(coins) + 1)]
# 初始化dp，价值为0时，不取硬币，也是一种方案
for i in range(len(coins) + 1):
dp[i][0] = 1
#这两个循环可以颠倒位置
for i, coin in enumerate(coins):
for j in range(amount+1):
# 此处对应注意点
if j - coin >= 0:
dp[i+1][j] = dp[i+1][j-coin] + dp[i][j]
else:
dp[i+1][j] = dp[i][j]
return dp[-1][-1]一维数组解法：
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
# 完全背包问题，组合数
dp = [0] * (amount + 1)
dp[0] = 1
# 先物品后背包，顺序不能颠倒
for coin in coins:
for i in range(coin, amount+1):
# 第10行相当于12，13行，把if写在for循环中
# for i in range(amount+1):
# if i-coin >= 0:
dp[i] += dp[i-coin]
return dp[-1]二维解法：
（推荐用一维做）
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
# 完全背包问题， 排列数
# dp[i][j]表示下标用0到i-1,能取到j-1的方案数
dp = [[0] * (target + 1) for _ in range(len(nums) + 1)]
for i in range(len(nums) + 1):
dp[i][0] = 1
# 先目标后物品
for j in range(1, target + 1):
for i in range(1, len(nums) + 1):
if j - nums[i-1] >= 0:
dp[i][j] = dp[-1][j-nums[i-1]] + dp[i-1][j]
else:
dp[i][j] = dp[i-1][j]
return dp[-1][-1]一维解法
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
# 完全背包问题， 排列数
# dp[i]表示能取到i-1的方案数
dp = [0] * (target + 1)
dp[0] = 1
# 因为求排列数，所以先背包，后物品
for i in range(1, target + 1):
for num in nums:
if i - num >= 0:
dp[i] += dp[i-num]
return dp[-1]评论 (0)
