目录
🍕题目70. 爬楼梯
🍔思路
拿到题目，不慌，先读题：
- 一共要爬 n 阶，所以n >= 0；
- 一次可以爬 1 或 2 个台阶；
- 问爬如果n 阶有多少种走法
比如n = 3 时 一共有三种 ： 2+1 1+1+1 1+2
因为每次只能爬 1级或 2 级，所以 f(x) 只能从 f(x - 1)和 f(x - 2)转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。
一般式子 f(n) = f(n-1) + f(n-2) 加上边界 n >= 2
🍟我一开始的想法：
暴力
# 暴力深搜 def climbStairs(self, n: int) -> int: if n == 0 or n == 1: return 1 return self.climbStairs(n - 1) + self.climbStairs(n - 2)
好家伙超时了
我们优化一下
🍟记忆递推法
-1 表示没有计算过，最大索引为 n，因此数组大小需要 n + 1
class Solution: # 记忆化递归，自顶向下 def climbStairs(self, n: int) -> int: def dfs(i: int, memo) -> int: if i == 0 or i == 1: return 1 if memo[i] == -1: memo[i] = dfs(i - 1, memo) + dfs(i - 2, memo) return memo[i] # memo: [-1] * (n - 1) # -1 表示没有计算过，最大索引为 n，因此数组大小需要 n + 1 return dfs(n, [-1] * (n + 1))
🍕题目 198. 打家劫舍
🍔思路
不能拿相邻的房间的钱
1）递推公式dp[i]=max(dp[i−2]+nums[i],dp[i−1])
我们再来考虑边界条件
2）边界条件为：
dp[0]=nums[0]
dp[1]=max(nums[0],nums[1])
只有一间房屋时候，则偷窃该房屋
只有两间房屋时候，选择其中金额较高的房屋进行偷窃
🍟动态规划
class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 size = len(nums) if size == 1: return nums[0] dp = [0] * size dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, size): dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) return dp[size - 1]
🍕题目120. 三角形最小路径和
🍔思路：
路线的选择，分两种
一种在旁边
if j==0: #最左边的情况
triangle[i][j]+=triangle[i-1][j]
elif j==i: #最右边的情况
triangle[i][j]+=triangle[i-1][j-1]一种在中间
triangle[i][j]+=min(triangle[i-1][j-1],triangle[i-1][j])
选上面两个最小的那个
🍟代码
class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: if len(triangle)==0: return 0 #动态规划 dp表示走到当前位置的时候的最小路径 for i in range(1,len(triangle)): for j in range(len(triangle[i])): if j==0: #最左边的情况 triangle[i][j]+=triangle[i-1][j] elif j==i: #最右边的情况 triangle[i][j]+=triangle[i-1][j-1] else: triangle[i][j]+=min(triangle[i-1][j-1],triangle[i-1][j]) return min(triangle[-1]) #返回最后一层最小的一个
