Leetcode-刷题笔记1-动态规划part06
目录
Leetcode 刷题笔记1 动态规划part06
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] = 0
for 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] = 0
squr = int(n ** 0.5)
for i in range(1, squr + 1):
i *= i
for 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] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j: i] in wordSet:
dp[j] = True
break
return dp[n]