文章目录
- 322.零钱兑换
- 279.完全平方数
- 139.单词拆分
322.零钱兑换
零钱看作是物品，和为背包，最少的硬币数量就是在dp[i-coin]+1 和dp[i]中找最小值，所以初始dp赋值为inf，dp[0]另外设置为0。
class Solution:def coinChange(self, coins: List[int], amount: int) -> int:dp = [float('inf')] * (amount + 1)dp[0] = 0for coin in coins:for i in range(coin, amount+1):dp[i] = min(dp[i-coin]+1, dp[i])if dp[-1] == float('inf'):return -1else:return dp[-1]
279.完全平方数
把小于等于n的完全平方数看作是物品，n是背包，其余和上一题一样。
class Solution:def numSquares(self, n: int) -> int:fullSquares = []start = 1while start**2 <= n:fullSquares.append(start**2)start += 1dp = [float('inf')] * (n+1)dp[0] = 0for square in fullSquares:for i in range(square, n+1):dp[i] = min(dp[i-square]+1, dp[i])return dp[-1]
139.单词拆分
dp数组为字符串中每一位是否能够被拆分，然后对于每一位去和单词做匹配，如果匹配的上并且前面对应的位置位True，则令这个位置也为True。
class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:l = len(s)dp = [False] * (l+1)dp[0] = Truefor i in range(l+1):for word in wordDict:word_len = len(word)if i-word_len>=0 and dp[i-word_len] and s[i-word_len:i] == word:dp[i] = Truereturn dp[-1]