代码随想录第38天

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:@cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）def dfs(i: int, c: int) -> int:if i < 0:return 0 if c == 0 else infif c < coins[i]:return dfs(i - 1, c)return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)ans = dfs(len(coins) - 1, amount)return ans if ans < inf else -1

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

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