LeetCode HOT100刷题笔记（十五）：动态规划

【如果笔记对你有帮助，欢迎关注&点赞&收藏，收到正反馈会加快更新！谢谢支持！】

ps：笔记和代码按本人理解整理，重思路

题目81: 爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

• 题意：一次只能爬1/2个台阶，总共有几种方法可以到第n层
• 关键：第 n 层的方法数 = 第 n-1 层的方法数 + 第 n-2 层的方法数
• 代码：

  class Solution: def climbStairs(self, n: int) -> int: a, b = 1, 1 # n-1 和 n-2 的方法数量 for _ in range(n-1): a, b = b, a+b return b

 题目82: 杨辉三角

118. 杨辉三角 - 力扣（LeetCode）

• 关键：左侧对齐
  
• 代码：

  class Solution: def generate(self, numRows: int) -> List[List[int]]: result = [[1] * (i + 1) for i in range(numRows)] for num in range(1, numRows): for i in range(1,num): result[num][i] = result[num-1][i-1]+result[num-1][i] return result

题目83: 打家劫舍

198. 打家劫舍 - 力扣（LeetCode）

• 题意：相邻房屋不能偷，求能偷的最大金额
• 关键：第 n 个的最大金额 = max( 第 n-1 个的最大金额, 第 n-2 个的最大金额 + 当前金额）
• 代码：

  class Solution: def rob(self, nums: List[int]) -> int: dp = [0]*(len(nums)+2) for idx, num in enumerate(nums): dp[idx+2] = max(dp[idx+1], dp[idx]+num) return dp[-1]

题目84: 完全平方数

279. 完全平方数 - 力扣（LeetCode）

• 题意：找出和为 n 的完全平方数的最少数量，完全平方数可重复（完全背包问题）
• 关键：第 n 个的最少数量 = min(第 n 个的最少数量，第 n - i^2 个的最少数量 + 1） for i^2 ≤ n
• 代码：

  class Solution: def numSquares(self, n: int) -> int: s = 1 squres = [] while s**2 <= n: squres.append(s**2) s += 1 dp = [float(\'inf\')]*(n+1) dp[0] = 0 for sq in squres: for c in range(sq, n+1): dp[c] = min(dp[c], dp[c-sq]+1) return dp[-1] if dp[-1]!=float(\'inf\') else -1 

题目85: 零钱兑换

322. 零钱兑换 - 力扣（LeetCode）

• 题意：找到总金额所需的 最少的硬币个数（完全背包问题）
• 关键：第 n 元的最少个数 = min（第 n 元的最少个数，第 n - c 元 的最少个数+ 1） for c in coins
• 代码：

  class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [float(\'inf\')]*(amount+1) dp[0] = 0 for num in range(1, amount+1): for coin in coins: if coin <= num:  dp[num] = min(dp[num], dp[num-coin]+1) return dp[-1] if dp[-1] != float(\'inf\') else -1

题目86: 单词拆分

139. 单词拆分 - 力扣（LeetCode）

• 题意：判断单词s是否可以拆分成字典中的单词，可以重复使用（完全背包问题）
• 关键：s[: n] 可拆分 = n > len(word) & s[: n-len(word)] 可拆分 & s[n-len(word): n] for word in 字典
• 代码：

  class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: dp = [0]*(len(s)+1) dp[0] = 1 for idx in range(1, len(s)+1): for word in wordDict: if len(word) <= idx and dp[idx-len(word)]==1 and s[idx-len(word):idx]==word:  dp[idx] = 1 return dp[-1]==1