代码随想录算法营Day42 ｜ 322. 零钱兑换，279. 完全平方数，139. 单词拆分

322. 零钱兑换

这道题先遍历物品也就是每个不同的硬币，然后遍历该硬币面值到目标值的dp数组，状态转移公式为dp[i] = min(dp[i],dp[i-coin]+1)

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,len(dp)):if dp[i-coin] != float('inf'):dp[i] = min(dp[i],dp[i-coin]+1)return dp[amount] if dp[amount] != float('inf') else -1

279. 完全平方数

这个背包的大小就是这个目标数，而物品则是每个小于等于该数平方根的所有数。

class Solution:def numSquares(self, n: int) -> int:dp = [0] * (n + 1)for i in range(1,n+1):minn = float('inf')for j in range(1,int(i**0.5)+1):minn = min(minn,dp[i-j*j])dp[i] = minn + 1return dp[n]

139. 单词拆分

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:wordDictSet = set(wordDict)dp = [False] * (len(s) + 1)dp[0] = Truefor i in range(1,len(s)+1):for j in range(i):if dp[j] and s[j:i] in wordDictSet:dp[i] = Truebreakreturn dp[len(s)]