代码随想录算法训练营Day 46 || 139.单词拆分、多重背包

139.单词拆分 

“139. 单词拆分” 是一个经典的动态规划问题，具体描述如下：

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

字符串 s 可以被空格拆分成一系列字典中出现的单词，单词可以在字典中重复使用多次，并且可以使用字典中全部的单词。

示例:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
 
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。
 
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

解题步骤

1. 定义状态：

   • 创建一个布尔数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符能否拆分成 wordDict 中的单词。

2. 初始化状态：

   • dp[0] = true，表示空字符串总是可以被拆分（即不拆分就是拆分成零个单词）。

3. 状态转移方程：

   • 对于每个 i 从 1 到 s.length()，遍历 j 从 0 到 i，检查字符串 s 的 j 到 i 部分是否存在于 wordDict 中：
     • 如果 dp[j] 是 true 且 s.substring(j, i) 在 wordDict 中，那么 dp[i] 也应当是 true。

4. 填充动态规划表：

   • 使用嵌套循环，外循环遍历字符串 s 的所有子字符串，内循环遍历当前子字符串的所有可能的拆分位置。

5. 返回结果：

   • 检查 dp[s.length()] 的值，如果为 true，表示整个字符串可以用 wordDict 中的单词拆分，否则不可以。

代码实现

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordSet = set(wordDict)  # 将列表转换为集合，以便于快速查找
        dp = [False] * (len(s) + 1)
        dp[0] = True
        
        for i in range(1, len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in wordSet:
                    dp[i] = True
                    break  # 找到一个有效的拆分点后，不需要继续检查更长的子字符串
        
        return dp[len(s)]

在这个代码中，dp 数组用来存储字符串 s 的每个子字符串是否可以被拆分。通过从前往后的动态规划方法，我们逐步构建出哪些部分的字符串可以由 wordDict 中的单词组成。最终，dp[len(s)] 给出了整个字符串 s 是否可以被拆分的答案。

多重背包

多重背包问题是背包问题的一个变体，在这个问题中，每种物品都有一定数量的限制，也就是说，每种物品不是只能取一次（0-1背包问题），也不是无限取（完全背包问题），而是有一个特定的最大数量。

问题描述

给定一个背包，它有一个固定的承重量 W。还有一系列物品 n，每个物品都有自己的价值 v[i] 和重量 w[i]，同时每个物品可以取的最大数量限制为 c[i]。目标是确定每种物品应该取多少个，使得背包中的物品总价值最大，同时不超过背包的承重量。

解题思路

多重背包问题可以通过动态规划来解决，解题思路与0-1背包和完全背包类似，但在状态转移方程上需要考虑每种物品的数量限制。

1. 定义状态：

   • 定义 dp[i][w] 表示对于前 i 种物品，当前背包重量为 w 时的最大价值。

2. 初始化状态：

   • 初始化 dp[0][...] 为0，因为没有物品时背包的价值为0。

3. 状态转移方程：

   • 对于每种物品 i，对于每个重量 w，遍历这种物品可能取的数量 k（从0到 c[i]）：
     • dp[i][w] = max(dp[i][w], dp[i-1][w-k*w[i]] + k*v[i]) 其中 w-k*w[i] >= 0
   • 这个状态转移方程表示，当前的最大价值可以是不取这个物品（即 dp[i-1][w]），也可以是取了 k 个这种物品之后的最大价值。

4. 计算顺序：

   • 从第一种物品开始，依次计算每种物品的状态，对于每种物品，从背包最大重量开始向下计算直至0。

5. 优化空间复杂度：

   • 与0-1背包问题一样，可以仅使用一维数组来优化空间复杂度。注意，由于物品的数量有限，更新时应该按重量从大到小的顺序来更新。