ppt网站哪家比较好_深圳坪山区地图_搜索引擎网站_bittorrentkitty磁力猫

leetcode 322 零钱兑换

由于本题所求为最少零钱数所以递推公式中应该为dp[ j ] = min(dp[ j ], dp[ j - 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 j in range(coin, amount + 1):if dp[j - coin] != float('inf'):dp[j] = min(dp[j], dp[j - coin] + 1)if dp[amount] == float('inf'):return -1 return dp[amount]

leetcode 279 完全平方数

需要注意物品的上界

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

leetcode 139 单词拆分

对于字符串的处理还不熟练

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