代码随想录 27（动态规划）

力扣 509.斐波那契数

思路

动态规划五部曲：

1. 确定dp数组已经下标的含义
2. 确定递推公式
3. 数组初始化
4. 确定遍历顺序
5. 举例推导dp数组

根据题目和五步曲，分析如下：

1. dp[i] 含义是：第 i 个斐波那契数是 dp[i]
2. 递推公式题目已经给出：dp[i] = dp[i-1] + dp[i-2]
3. 数组初始化题目已经给出：dp[0] = 0 、dp[1] = 1
4. 遍历顺序是从前往后遍历
5. 略

解法

public int fib(int n) { if (n <= 1) { return n; } int[] dp = new int[n+1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }

这个解法，可以遍历n次，时间复杂度是On，定义一个n+1的数组，空间复杂度是O（n+1）。实际上只需要定义一个长度为2的数组，总和可以用一个变量sum来维护，这样的话时间复杂度不变，但是空间复杂度为O1。

// 优化之后没有用数组，直接优化成变量 public int fib(int n) { if (n <= 1) { return n; } int a = 0, b = 1, sum = 0; for (int i = 2; i <= n; i++) { sum = a + b; a = b; b = sum; } return sum; }

力扣 70.爬楼梯

思路

动态规划五步曲：

1. 确定动态数组dp，以及下标的含义
2. 确定递推公式
3. 确定初始化值
4. 确定遍历顺序
5. 举例推导数组

一开始博主想的是 dp[i] 数组是每次爬多少阶，i 下标是第 i 阶。但是这样的思路不对，因为题目要求的是多少种爬楼梯方法，这样想可以到达楼顶，但是无法得到有多少种方法。

下面按照五步曲，进行正确的推理：

1. dp[i] 是爬到第 i 层有dp[i] 种爬楼梯的方法，
2. dp[i] 的时候有两种情况：在dp[i-1] 爬一层，或者在dp[i-2] 爬二层。
   因此递推公式是 dp[i] = dp[i-1] + dp[i-2]
3. 题目条件：1<=n<=45，所以不用考虑dp[0] ，那么dp[1] = 1；dp[2] = 2。
4. 遍历顺序是从前往后
5. n = 3时候，dp[3] = dp[2] + dp[1] = 3

解法

public int climbStairs(int n) { if (n<=2) { return n; } int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }

遍历n-3次，时间复杂度是On，定义数组长度为n+1，那么空间复杂度是On，那可不可以像上一题那样优化空间复杂度呢？其实是可以的，不难看出，答案跟上一题是几乎一样，那么优化应该没有问题。

public int climbStairs(int n) { if (n<=2) { return n; } int sum = 0, a = 1, b = 2; for (int i = 3; i <= n; i++) { sum = a + b; a = b; b = sum; } return sum; }

力扣 746.使用最小花费爬楼梯

思路

解法