算法记录 | Day38 动态规划

对于动态规划问题，将拆解为如下五步曲

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

509.斐波那契数

思路：

1. 确定dp数组（dp table）以及下标的含义：dp[i]的定义为：第i个数的斐波那契数值是dp[i]

2. 确定递推公式：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]

3. dp数组如何初始化：dp[0] = 0，dp[1] = 1

4. 确定遍历顺序：从前到后遍历

5. 举例推导dp数组：推导一下，当N为10的时候，dp数组应该是如下的数列：

   0 1 1 2 3 5 8 13 21 34 55

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

70.爬楼梯

思路：

1. 确定dp数组（dp table）以及下标的含义：dp[i]： 爬到第i层楼梯，有dp[i]种方法

2. 确定递推公式：

   dp[i] 可以有两个方向推出来。

   首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。

   还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。

3. dp数组如何初始化：dp[0] = 1，dp[1] = 1

4. 确定遍历顺序：从前到后遍历

5. 举例推导dp数组：

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

746.使用最小花费爬楼梯

思路：

1. 确定dp数组（dp table）以及下标的含义：dp[i]爬到楼顶的花费

2. 确定递推公式：

   dp[i - 1]，到上i-1层楼梯，花费dp[i - 1]，i-1到i花费dp[i - 1]+cost[i-1]

   dp[i - 2]，上i-2层楼梯，花费dp[i - 2]，i-2到i花费dp[i - 2]+cost[i-2]

   dp [i] = min(dp[i - 1]+cost[i-1]，dp[i - 2]+cost[i-2])

3. dp数组如何初始化：dp[0] = 0，dp[1] = 0

   **注意：**题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 从 到达 第 0 个台阶是不花费的，但从 第0 个台阶 往上跳的话，需要花费 cost[0]。

4. 确定遍历顺序：从前到后遍历

5. 举例推导dp数组：

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:n = len(cost) dp = [0 for _  in range(n+1)]if n < 1:return 0dp[0] = 0dp[1] = 0for i in range(2, n+1):dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])return dp[n]