＜代码随想录＞ 算法训练营-2024.12.20

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:# dp[i][j]表示 提供到coins[i]的硬币，总金额为j的最少硬币个数 硬币个数无限，完全背包# 有两种取值，一种是取dp[i-1][j] 另一种是如果j比当前面额小，则可以取dp[m][n-coins[m]]+1size = len(coins)dp = [[10**4 + 1] * (amount + 1) for _ in range(size)]for i in range(size):dp[i][0] = 0for m in range(size):for n in range(1, amount + 1):if coins[m] <= n:dp[m][n] = min(dp[m - 1][n], dp[m][n - coins[m]] + 1)else:dp[m][n] = dp[m - 1][n]return -1 if dp[-1][-1] == 10**4 + 1 else dp[-1][-1]

class Solution:def numSquares(self, n: int) -> int:#预处理完全平方数数组# 题目变成，完全背包中达到目标值的最少元素个数nums = []temp = 1while temp**2 <= n:nums.append(temp**2)temp += 1if nums[-1] == n:return 1size = len(nums)dp = [[10**4 + 1] * (n + 1) for _ in range(size)]for i in range(size):dp[i][0] = 0for i in range(size):for j in range(1, n + 1):if nums[i] <= j:dp[i][j] = min(dp[i - 1][j], dp[i][j - nums[i]] + 1)else:dp[i][j] = dp[i - 1][j]return -1 if dp[-1][-1] == 10**4 + 1 else dp[-1][-1]

class Solution(object):def wordBreak(self, s, wordDict):# 先对单词按长度排序wordDict.sort(key=lambda x: len(x))n = len(s)dp = [False] * (n + 1)dp[0] = True# 遍历背包for i in range(1, n + 1):# 遍历单词for word in wordDict:# 简单的 “剪枝”if len(word) > i:breakdp[i] = dp[i] or (dp[i - len(word)] and s[i - len(word): i] == word)return dp[-1]