代码随想录算法营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] = 0 for 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 + 1 return dp[n] 139. 单词拆分 class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: wordDictSet = 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 wordDictSet: dp[i] = True break return dp[len(s)]