本文主要是介绍【力扣一刷】代码随想录day38（动态规划part1：509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
【动态规划理论基础】
【509. 斐波那契数】简单题
方法一 用额外的数组存储每个状态
方法二 用2个遍历存储前两个状态（减小空间复杂度）
【70. 爬楼梯】简单题
【746. 使用最小花费爬楼】简单题
【动态规划理论基础】
1、定义：英文为Dynamic Programming，简称DP
2、步骤：
- 确定变量 f(i) 的含义
- 确定递推公式：如 f(i) 和 f(i-1)、f(i-2) 的关系，自变量的数量根据具体情况而定
- 如何初始化
- 确定遍历顺序
- 举例推导dp数组
【509. 斐波那契数】简单题
方法一 用额外的数组存储每个状态
class Solution {public int fib(int n) {if (n <= 1) return n;int[] list = new int[n+1];list[0] = 0;list[1] = 1;for (int i = 2; i < n+1; i++){list[i] = list[i-1] + list[i-2];}return list[n];}
}- 时间复杂度: O(n)
- 空间复杂度: O(n)
方法二 用2个遍历存储前两个状态（减小空间复杂度）
注意：for循环主要是控制计算的次数，初始值已经知道 f(0) 和 f(1) 的值了，计算从 f(2) 到 f(n) 的值，i 从2开始，直至n，共计算 n - 2 + 1 = n - 1 次。
class Solution {public int fib(int n) {if (n <= 1) return n;int x1 = 0;int x2 = 1;int y = 0;for (int i = 2; i < n+1; i++){y = x1 + x2;x1 = x2;x2 = y;}return y;}
}- 时间复杂度: O(n)
- 空间复杂度: O(1)
【70. 爬楼梯】简单题
思路：为 n = 1 和 n = 2 构造前面两个变量的值，使其都可以通过for循环计算
对于 n = 1，结果为1，对于 n = 2，结果为2，可以推出 n = 0，结果为 2 - 1 = 1。
对 n = 1 来说，除了 n = 0外还差一个 f(i-2)的值，可以初始化为 1 - 1 = 0。
class Solution {public int climbStairs(int n) {int x1 = 0;int x2 = 1;int y = 0;for (int i = 1; i <= n; i++){y = x1 + x2;x1 = x2;x2 = y;}return y;}
}- 时间复杂度: O(n)
- 空间复杂度: O(1)
【746. 使用最小花费爬楼】简单题
思路：
1、分别计算从第 i 阶起跳至少要花费的钱。
2、楼顶肯定是第 cost.length - 1 阶或者第 cost.length - 2 阶楼梯起跳跳上去的，所以返回这两个之中的最小值即可。
class Solution {public int minCostClimbingStairs(int[] cost) {int x1 = cost[0];int x2 = cost[1];int y = 0;for (int i = 2; i < cost.length; i++){y = Math.min(x1, x2) + cost[i]; // 计算从第i阶楼梯起跳最少要花费的钱x1 = x2;x2 = y;}return Math.min(x1, x2);}
}- 时间复杂度: O(n)
- 空间复杂度: O(1)
这篇关于【力扣一刷】代码随想录day38（动态规划part1：509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
