算法记录 | Day46 动态规划网站首页 学无止境

算法记录 | Day46 动态规划

是菜鸡小小陈啊 2023-07-01 04:00:02

简介算法记录 | Day46 动态规划

139.单词拆分

思路：

1.确定dp数组以及下标的含义

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

2.确定递推公式

如果 s[0: j] 可以拆分为单词（即 dp[j] == True），并且字符串 s[j: i] 出现在字典中，则 dp[i] = True。
如果 s[0: j] 不可以拆分为单词（即 dp[j] == False），或者字符串 s[j: i] 没有出现在字典中，则 dp[i] = False。

3.dp数组如何初始化:

长度为 0 的字符串 s[0: i] 可以拆分为单词，即 dp[0] = True。

4.确定遍历顺序:题目中说是拆分为一个或多个在字典中出现的单词，所以这是完全背包。本题其实求的是排列数。先遍背包，再遍历物品。

5举例推导dp[i]:

以输入: s = “leetcode”, wordDict = [“leet”, “code”]为例，dp状态如图：

139.单词拆分

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        size = len(s)
        dp = [False for _ in range(size + 1)]
        dp[0] = True
        for i in range(size + 1):
            for j in range(i):
                if dp[j] and s[j: i] in wordDict:
                    dp[i] = True
        return dp[size]

多重背包

多重背包问题：有 n 种物品和一个最多能装重量为 W的背包，第 i种物品的重量为weight[i]，价值为value[i]，件数为count[i]。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？

03.背包问题知识（三） | 算法通关手册 (itcharge.cn)

1.确定dp数组以及下标的含义定义状态：dp[w]将物品装入最多能装重量为w的背包中，可以获得的最大价值。

2.状态转移方程:dp[w]=max{dp[w-kxweight[i-1]]+kxvalue[]i-1}

3.初始条件:无论背包载重上限为多少，只要不选择物品，可以获得的最大价值一定是 0，即，dp[w]=0，

class Solution: 
    # 思路 2：动态规划 + 滚动数组优化
    def multiplePackMethod2(self, weight: [int], value: [int], count: [int], W: int):
        size = len(weight)
        dp = [0 for _ in range(W + 1)]
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 逆序枚举背包装载重量（避免状态值错误）
            for w in range(W, weight[i - 1] - 1, -1):
                # 枚举第 i - 1 种物品能取个数
                for k in range(min(count[i - 1], w // weight[i - 1]) + 1):
                    # dp[w] 取所有 dp[w - k * weight[i - 1]] + k * value[i - 1] 中最大值
                    dp[w] = max(dp[w], dp[w - k * weight[i - 1]] + k * value[i - 1])
                
        return dp[W]