代码随想录算法训练营Day32

动态规划基础知识
力扣509.斐波那契数列【easy】
力扣70.爬楼梯【easy】
力扣198.打家劫舍【medium】

一、动态规划基础知识

1、动态规划的解题步骤

• 确定dp数组（dp table）以及下标的含义
• 确定递推公式
• dp数组如何初始化
• 确定遍历顺序
• 举例推导dp数组

2、核心思想

• 把已经解决的小问题的结果保存下来，用来解决更大的问题
• 动态规划 = 记住以前的结果 + 用它们推导新的结果，避免重复劳动！

3、常见定义

• 最优子结构（Optimal Substructure）
  • 动态规划问题通常具有最优子结构，即一个问题的最优解可以通过子问题的最优解组合而成。
  • 换句话说，整体问题的最优解包含了其子问题的最优解。
• 重叠子问题（Overlapping Subproblems）
  • 动态规划算法会多次计算相同的子问题，重叠子问题意味着在不同的计算中会遇到相同的子问题，因此可以将子问题的结果存储起来，以避免重复计算。
• 状态表示
  • 动态规划的核心思想是通过定义状态来表示子问题的解，进而通过状态的转移来得到问题的最优解。
• 递推公式
  • 对于每一个子问题，都有一个递推公式，定义了如何通过之前计算的子问题的解来得到当前子问题的解。
• 边界条件
  • 边界条件是递推的基础，通常表示最小子问题的解，例如一个问题的最小解（通常是基础情况或初始值）。

4、灵神

---

二、力扣509.斐波那契数列【easy】

题目链接：力扣509.斐波那契数列

视频链接：代码随想录

1、思路

• dp五部曲
• 时间复杂度：$O(n)$

2、代码

class Solution:def fib(self, n: int) -> int:if n <= 1:return ndp = [0] * (n+1)dp[0] = 0dp[1] = 1for i in range(2, n+1):dp[i] = dp[i-1] + dp[i-2]return dp[n]

---

三、力扣70.爬楼梯【easy】

题目链接：力扣70.爬楼梯
视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• 和大家结舍一样的三个版本做法

• 分类讨论：

  • 如果最后一步爬了 1 个台阶，那么我们得先爬到 i−1，要解决的问题缩小成：从 0 爬到 i−1 有多少种不同的方法。
  • 如果最后一步爬了 2 个台阶，那么我们得先爬到 i−2，要解决的问题缩小成：从 0 爬到 i−2 有多少种不同的方法。

• 由于这两种方法是互相独立的（爬的台阶个数不同），所以根据加法原理，从 0 爬到 i 的方法数等于这两种方法数之和，即 $dfs(i)=dfs(i-1)+dfs(i-2)$

• 时间复杂度：$O(n)$

2、代码

class Solution:def climbStairs(self, n: int) -> int:# @cache# def dfs(i):#     if i <= 1:#         return 1#     return dfs(i-1) + dfs(i-2)# return dfs(n)# dp = [0] * (n + 1)# dp[0] = dp[1] = 1# for k in range(2, n + 1):#     dp[k] = dp[k - 1] + dp[k - 2]# return dp[n]f0 = f1 = 1for _ in range(2,n + 1):new_f = f0 + f1f0 = f1f1 = new_freturn f1

---

四、力扣198.打家劫舍【medium】

题目链接：力扣198.打家劫舍

视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• 先介绍了回溯的做法，还是把问题归为子问题，可以用子问题表示原问题
• 回溯时间复杂度太高，呈指数级，超时
• 将重复计算的节点储存起来，发现我们其实只要计算n个结点，大大节约了时间复杂度，这就是法一
• 我们将递归中的递去掉，只留下归，相当于只要自下而上的做法，这个时候较为递推，这就是我们的动态规划了，法二
• 前两个的空间复杂度都是$O(n)$，我们发现其实计算新节点的时候只和前两个结点相关，所以“动态窗口”，只储存需要的前两个计算结果，空间复杂度就降下来了，法三
• 时间复杂度：$O(n)$
• 空间复杂度：前两个$O(n)$ ，第三个优化到 $O(1)$

2、代码

• 递归搜索 + 保存计算结果 = 记忆化搜索

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)cashe = [-1] * ndef dfs(i):if i < 0:return 0if cashe[i] != -1:return cashe[i]res = max(dfs(i-1), dfs(i-2) + nums[i])cashe[i] = resreturn cashe[i]return dfs(n-1)

• 动态规划：去掉递归中的递，只保留归

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

• 空间优化：只保留就近需要的前两个值，空间复杂度从$O(n)$ 降到$O(1)$

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)f0 = f1 = 0for i, x in enumerate(nums):new_f = max(f1, f0 + x)f0 = f1f1 = new_freturn new_f

---