代码随想录打卡|Day28 动态规划（理论基础、斐波那契数列、爬楼梯、使用最小花费爬楼梯）

动态规划 Part01

理论基础

代码随想录讲解链接
视频讲解链接

---

斐波那契数

力扣题目链接
代码随想录链接
视频讲解链接

题目描述： 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

动态规划五部曲：

1. dp[i]定义：dp[i]是第i个斐波那契数的值。
2. 递推公式：dp[i] = dp[i-1] + dp[i-2];
3. dp数组的初始化： dp[0] = 0;dp[1] = 1;
4. 遍历顺序：从头到尾遍历
5. 打印数组

代码如下：

class Solution {public int fib(int n) {// 定义dp数组int[] F = new int[n + 1];for(int i = 0 ; i < n + 1; i++){// dp数组的填充方式if(i == 0) F[i] = 0;else if(i == 1)F[i] = 1;elseF[i] = F[i - 1] + F[i - 2];}return F[n];}
}

---

爬楼梯

力扣题目链接
代码随想录链接
视频讲解链接

题目描述： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

动态规划五部曲：
1.dp[i]：当楼梯数为i的时候，从0到i的可行的爬楼方式。
2.递推公式：dp[i] = dp[i - 1] + dp[i-2]；
3.dp数组初始化：dp[0] = 1;dp[1] = 2;
4.遍历顺序：从头到尾遍历
5.打印数组

代码如下：

class Solution {public int climbStairs(int n) {int[] dp = new int[n];for(int i = 0 ; i < n ; i++){if(i == 0)dp[i] = 1;else if(i == 1)dp[i] = 2;elsedp[i] = dp[i - 1] + dp[i - 2];}return dp[n - 1];}
}

---

使用最小花费爬楼梯

力扣题目链接
代码随想录链接
视频讲解链接

题目描述： 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

动态规划五步：

1. dp[i]：当登上第i层所需的最小消费
2. 递推公式：我们在第i层的花费为dp[i]=min(dp[i - 1] + cost[i],dp[i - 2] + cost[i - 2])；
3. 初始化：我们可以从下标0开始或者下标1开始，所以dp[0] = 0;dp[1] = 0;
4. 遍历顺序
5. 打印

代码如下：

站在当前楼层不收费（若楼层有i层，那么i+1层才是收费结果）

class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp = new int[cost.length + 1];dp[0] = 0 ;dp[1] = 0;for(int i = 2 ; i <= cost.length ; i++){dp[i] = Math.min(dp[i - 1] + cost[i - 1] ,dp[i - 2] + cost[i -2]);}return dp[cost.length];}
}

站在当前楼层收费（第i层即收费结果）

// class Solution {
//     public int minCostClimbingStairs(int[] cost) {
//         int[] dp = new int[cost.length + 1];
//         dp[0] = 0 ;
//         dp[1] = 0;//         for(int i = 2 ; i <= cost.length ; i++){
//                 dp[i] = Math.min(dp[i - 1] + cost[i - 1] ,dp[i - 2] + cost[i -2]);
//         }
//         return dp[cost.length];
//     }
// }class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp = new int[cost.length];dp[0] = cost[0];dp[1] = cost[1];for(int i = 2 ; i < cost.length ; i++){dp[i] = Math.min(dp[i - 1]  ,dp[i - 2]) + cost[i];}return Math.min(dp[cost.length - 1],dp[cost.length - 2]);}
}

状态压缩（用变量代替数组，减小空间复杂度）

// 状态压缩，使用三个变量来代替数组
class Solution {public int minCostClimbingStairs(int[] cost) {// 以下三个变量分别表示前两个台阶的最少费用、前一个的、当前的。int beforeTwoCost = 0, beforeOneCost = 0, currentCost = 0;// 前两个台阶不需要费用就能上到，因此从下标2开始；因为最后一个台阶需要跨越，所以需要遍历到cost.lengthfor (int i = 2; i <= cost.length; i ++) {// 此处遍历的是cost[i - 1]，不会越界currentCost = Math.min(beforeOneCost + cost[i - 1], beforeTwoCost + cost[i - 2]);beforeTwoCost = beforeOneCost;beforeOneCost = currentCost;}return currentCost;}
}

---