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

力扣 509.斐波那契数思路动态规划五部曲确定dp数组已经下标的含义确定递推公式数组初始化确定遍历顺序举例推导dp数组根据题目和五步曲分析如下dp[i] 含义是第 i 个斐波那契数是 dp[i]递推公式题目已经给出dp[i] dp[i-1] dp[i-2]数组初始化题目已经给出dp[0] 0 、dp[1] 1遍历顺序是从前往后遍历略解法public int fib(int n) { if (n 1) { return n; } int[] dp new int[n1]; 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定义一个n1的数组空间复杂度是On1。实际上只需要定义一个长度为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.爬楼梯思路动态规划五步曲确定动态数组dp以及下标的含义确定递推公式确定初始化值确定遍历顺序举例推导数组一开始博主想的是 dp[i] 数组是每次爬多少阶i 下标是第 i 阶。但是这样的思路不对因为题目要求的是多少种爬楼梯方法这样想可以到达楼顶但是无法得到有多少种方法。下面按照五步曲进行正确的推理dp[i] 是爬到第 i 层有dp[i] 种爬楼梯的方法dp[i] 的时候有两种情况在dp[i-1] 爬一层或者在dp[i-2] 爬二层。因此递推公式是 dp[i] dp[i-1] dp[i-2]题目条件1n45所以不用考虑dp[0] 那么dp[1] 1dp[2] 2。遍历顺序是从前往后n 3时候dp[3] dp[2] dp[1] 3解法public int climbStairs(int n) { if (n2) { 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定义数组长度为n1那么空间复杂度是On那可不可以像上一题那样优化空间复杂度呢其实是可以的不难看出答案跟上一题是几乎一样那么优化应该没有问题。public int climbStairs(int n) { if (n2) { 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.使用最小花费爬楼梯思路解法