这是本节的多页打印视图。 .

算法

记录一些刷leetcode的算法总结

1: 动态规划背包问题总结

记录一些刷leetcode的算法总结。

1 - 动态规划背包问题总结

动态规划背包问题的常见题型的解题思路和代码实现

背包问题总结

一共有2种背包:
- 01背包
- 完全背包
一共有4种求解目标:
- 求最大价值
- 求组合数
- 求排列数
- 给target,求最少/最多的物品数量

其中01背包不考虑排列数,完全背包不考给出target的最多物品数量

最大价值题型

题型1:01背包(最大价值)

def knap01(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):              # 物品外循环
        for j in range(capacity, w - 1, -1):       # 背包倒序
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[capacity]

416. 分割等和子集

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2: return False
        target = total // 2
        dp = [0] * (target + 1)
        for num in nums:                          # 物品
            for j in range(target, num - 1, -1):  # 背包倒序
                dp[j] = max(dp[j], dp[j - num] + num)
        return dp[target] == target

题型2:完全背包(最大价值)

def knapComplete(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):           # 物品外循环
        for j in range(w, capacity + 1):        # 背包正序
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[capacity]

这个题型在LeetCode上暂无对应题目

组合数题型

题型3:01背包 + 组合数

# 速查模板
def knap01_comb(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1
    for num in nums:                             # 物品外循环
        for j in range(target, num - 1, -1):     # 背包倒序
            dp[j] += dp[j - num]
    return dp[target]

494. 目标和

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if abs(target) > total or (total + target) % 2: return 0
        bag = (total + target) // 2
        dp = [0] * (bag + 1)
        dp[0] = 1
        for num in nums:                         # 物品
            for j in range(bag, num - 1, -1):    # 背包倒序
                dp[j] += dp[j - num]
        return dp[bag]

题型4:完全背包 + 组合数

# 速查模板
def complete_comb(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:                          # 物品外循环
        for j in range(coin, amount + 1):       # 背包正序
            dp[j] += dp[j - coin]
    return dp[amount]

518. 零钱兑换 II

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:                      # 物品
            for j in range(coin, amount + 1):   # 背包正序
                dp[j] += dp[j - coin]
        return dp[amount]

排列数题型

题型5:完全背包 + 排列数

# 速查模板
def complete_perm(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1
    for j in range(1, target + 1):              # 背包外循环
        for num in nums:                        # 物品内循环
            if j >= num:
                dp[j] += dp[j - num]
    return dp[target]

377. 组合总和 Ⅳ

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for j in range(1, target + 1):          # 背包外循环
            for num in nums:                    # 物品内循环
                if j >= num:
                    dp[j] += dp[j - num]
        return dp[target]

最少/最多物品数量题型

题型6:01背包 + 最少/最多物品数量

def knap01_max_len(nums, target):
    dp = [-float('inf')] * (target + 1)         # 初始化为负无穷
    dp[0] = 0
    for num in nums:                            # 物品外循环
        for j in range(target, num - 1, -1):    # 背包倒序
            dp[j] = max(dp[j], dp[j - num] + 1)
    return dp[target] if dp[target] != -float('inf') else -1

def knap01_min_len(nums, target):
    dp = [float('inf')] * (target + 1)          # 初始化为正无穷
    dp[0] = 0
    for num in nums:                            # 物品外循环
        for j in range(target, num - 1, -1):    # 背包倒序
            dp[j] = min(dp[j], dp[j - num] + 1)
    return dp[target] if dp[target] != float('inf') else -1

2915. 和为目标值的最长子序列的长度

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        dp = [-float('inf')] * (target + 1)
        dp[0] = 0
        for num in nums:                          # 每个数字只能用一次
            for j in range(target, num - 1, -1):  # 倒序遍历(01背包)
                dp[j] = max(dp[j], dp[j - num] + 1)
        return dp[target] if dp[target] != -float('inf') else -1

题型7:完全背包 + 最少物品数量

def complete_min_len(coins, amount):
    dp = [float('inf')] * (amount + 1)          # 初始化为正无穷
    dp[0] = 0
    for coin in coins:                          # 物品外循环
        for j in range(coin, amount + 1):       # 背包正序
            dp[j] = min(dp[j], dp[j - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

322. 零钱兑换

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for coin in coins:                       # 物品
            for j in range(coin, amount + 1):    # 背包正序
                dp[j] = min(dp[j], dp[j - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1