代码随想录算法训练营第三十八天 | 322.零钱兑换 279.完全平方数 139.单词拆分 多重背包以及背包总结

LeetCode 322.零钱兑换：

文章链接
题目链接：322.零钱兑换

思路：

首先分析题目，每种硬币的数量是无限的，因此为完全背包问题；又要求返回的是最少硬币个数，因此与组合数/排列数无关，先背包后物品还是先物品后背包均可，此处采用先物品后背包的方式

• ① dp数组及下标的含义
  dp[j] : 凑成背包金额为 j 所需的最少硬币个数为dp[j]
• ② 递推式
  那么依据是否选择coins[i]来分类
  如果选择coins[i] , 那么硬币个数为dp[j - coins[i]] + 1
  如果不选coins[i]，那么硬币个数为dp[j]
  求最少硬币个数，因此是两个求min
  dp[j] = min(dp[j], dp[j - coins[i]] + 1)
• ③ 初始化
  由例子可知，dp[0]=0，可以凑成总金额为0的硬币个数为0，其余非0初始化为"inf"，避免初始化对递推式产生影响。
• ④ 遍历顺序
  由前面题目分析可知，遍历顺序为先物品后背包，且均为顺序遍历
• ⑤ 举例
  

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)
        # 返回结果
        if dp[amount] == float('inf'):
            return -1
        return dp[amount]
        

LeetCode 279.完全平方数：

文章链接
题目链接：279.完全平方数

思路：

首先分析题目：给定一个整数n，求和为n的最少完全平方数的数目，且加和为n的完全平方数可重复，因此为完全背包问题，且要求的是最少，因此可以认为是上一题的改编。
区别在于，本题没有直接给出coins数组，但是分析可知，物品的重量/价值为 [1, int(sqrt(n))]中每个数的平方

• ① dp数组及下标的含义
  dp[j] : 凑成背包重量/价值为 j 所需的最少完全平方数个数为dp[j]
• ② 递推式
  将上一题中是否选择coins[i]修改为了 i^2，其余相同
  dp[j] = min(dp[j], dp[j - i ^ 2] + 1)
• ③ 初始化
  dp[0] = 0，其余非0初始化为最大值 inf
• ④ 遍历顺序
  由前面题目分析可知，遍历顺序为先物品后背包，且均为顺序遍历（先背包后物品也可以）
• ⑤ 举例
  

"""
先物品后背包
"""
class Solution:
    def numSquares(self, n: int) -> int:
        maxi = int(sqrt(n)) # 物品重量的取值范围
        if n == maxi * maxi:
            return 1
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for i in range(1, maxi + 1):
            powi = i * i
            for j in range(powi, n + 1):
                dp[j] = min(dp[j], dp[j - powi] + 1)
        return dp[n]
        
"""
先背包后物品
"""
class Solution:
    def numSquares(self, n: int) -> int:
        maxi = int(sqrt(n)) # 物品重量的取值范围
        if n == maxi * maxi:
            return 1
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for j in range(1, n + 1):
            i = 1
            while i * i <= j:
                dp[j] = min(dp[j], dp[j - i * i] + 1)
                i += 1
        return dp[n]
        

LeetCode 139.单词拆分：

文章链接
题目链接：139.单词拆分

思路

首先分析题目：s是否可以由字典中的单词拼接得到，且字典中的单词可以重复使用，因此是完全背包问题，并且拼接得到，因为拼接有先后顺序，因此本题为排列，遍历顺序应当为先背包后物品

• ① dp数组及下标含义
  dp[j]表示s[0:j]能否由字典中的单词拼接得到，为了便于初始化，因此s[j]是取不到的，从而dp[0]可以初始化为True
• ② 递推式
  按照wordDict[i]是否取来分类
  如果取wordDict[i]，那么应当判断s[j - wordDict[i] : j] == wordDict[i] 与 dp[j - wordDict[i]]（dp[j] 判断的是s[0:j]，取不到s[j]）（本质上是判断截取到的单词是否与词典中的相同，且截取后的部分是否可以被词典中的单词所拼接得到）
  如果不取wordDict[i]，那么dp[j] = dp[j]
  因为只需要判断s是否可以由字典中的单词构成，因此对于分出的类的结果是取 or
  dp[j] = dp[j] or (s[j - len(wordDict[i])] == wordDict[i] and dp[j - len(wordDict[i])])
• ③ 初始化
  dp[0] = True，其余非0初始化为False，避免初始化对递推结果产生影响
• ④ 遍历方式
  由前面题目分析可知，本题应当是求排列，遍历方式为先背包后物品，且均为顺序遍历
• ⑤ 举例
  
  有一些需要注意的地方：
  1）首先因为遍历顺序为先背包后物品，所以可能出现len(s[0:j]) 即 j < len(wordDict[i])的情况，并且这种情况也不方便直接在第二层遍历中去除（即改range），因此在第二层循环体内加条件判断去除；
  2）其次，由递推公式可知，需要判断s[j - len(wordDict[i])] == wordDict[i]，实际上在递推公式前可以加剪枝，直接判断s[j - 1] == wordDict[i][-1]，如果不相等，那么后面不需要递推公式判断，直接就是False；否则才使用递推公式得到dp[j]

"""
第二层遍历是遍历的词典中的词
"""
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        lens = len(s)
        # dp[j]表示s[0:j]能否由字典中的单词拼接得到，其中s[j]取不到
        dp = [False] * (lens + 1)
        dp[0] = True
        # 递推，分析题目得到是求排列，先背包后物品
        for j in range(1, lens + 1):
            for word in wordDict:
            	# 先进行判断s[0:j]的长度和剪枝
                if len(word) > j or word[-1] != s[j - 1]:
                    continue
                dp[j] = dp[j] or (dp[j - len(word)] and s[j - len(word):j] == word)
        return dp[lens]
      
不太确定：
时间复杂度为O(m * n * L)
其中m = len(wordDict)， n = len(s)， L为词典中单词的最大长度。
空间复杂度为O(n)

"""
第二层遍历是对s[j]的后半部分进行剪切
1. 递推式还可以这么理解 dp[j] = dp[j] or (s[i:j] in wordSet and dp[i])
2. 对dp[j]的后半部分进行切分，i 为切分的开始位置，i 的范围为[0, j - 1]（双闭），
3. 判断s[i:j]是否在词典中出现过，且dp[i]是否能由词典中的词拼接得到
"""
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        lens = len(s)
        wordSet = set(wordDict)
        # dp[j]表示s[0:j]能否由字典中的单词拼接得到，其中s[j]取不到
        dp = [False] * (lens + 1)
        dp[0] = True
        # 递推，分析题目得到是求排列，先背包后物品
        for j in range(1, lens + 1):
            for i in range(j):
                if dp[i] and s[i:j] in wordSet:
                    dp[j] = True
        return dp[lens]
    
不太确定
时间复杂度为O(n^2)
空间复杂度为O(n)    

实现过程中遇到的问题：

两个代码时间复杂度的分析

多重背包：

有N种物品和一个容量为V的背包。第 i 种物品最多有Mi件可用，每件耗费的空间为Ci，价值为Wi。求解将哪些物品装入背包可使得这些物品耗费的的空间总和不超过背包容量，且价值总和最大。
多重背包与01背包相似。只要将多重背包中，每个物品最多有Mi件可用，将Mi件分隔开，就变成了一个01背包问题。
题目链接：卡码网 56

class Solution():
    def multiBag(self, bagWeight, N, weight, value, nums):
        dp = [0] * (bagWeight + 1)
        # 遍历
        for i in range(N):  # 先遍历物品
            #print("i: " + str(i))
            for j in range(bagWeight, weight[i] - 1, -1):   # 再逆序遍历背包
                for k in range(1, nums[i] + 1): # 需要加一个遍历物品数量的
                	# 如果大于背包容量直接跳出循环
                    if j < k * weight[i]:
                        break
                    dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i])
                #print("j: " + str(j) + " dp[j]: " + str(dp[j]))
            #print()
        return dp[-1]


bagWeight, N = [int(x) for x in input().split()]
weight = [int(x) for x in input().split()]
value = [int(x) for x in input().split()]
nums = [int(x) for x in input().split()]
solution = Solution()
print(solution.multiBag(bagWeight, N, weight, value, nums))

实现过程中遇到的问题：

首先要想到，多重背包中添加第三层循环k，其次注意range为左闭右开，因此是range(1, nums[i] + 1)，最后出现错误就打印dp数组

背包总结：

文章链接

学习收获：

完全背包的应用，明确递推公式和遍历顺序，借用多重背包复习了01背包问题，以及完全背包的组合数/排列数的内外层遍历先后顺序，最后的单词拆分第二层循环既可以是词典，也可以是对s[j]的后半部分的划分