代码随想录算法训练营Day 46|动态规划part08|139.单词拆分、多重背包、背包问题总结篇

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

---

---

139.单词拆分

题目链接

一、法一

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        # dp[i]表示长度为i的字符串是否可以用字符串列表表示01
        dp=[0]*(len(s)+1)
        dp[0]=1
        for j in range(1,len(s)+1):
            for i in range(len(wordDict)):
                if j>=len(wordDict[i]):
                    dp[j]=dp[j] or dp[j-len(wordDict[i])] and s[j-len(wordDict[i]):j]==wordDict[i]
        return True if dp[len(s)]==1 else False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

多重背包

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。

---