746. 使用最小花费爬楼梯

╰半夏微凉° 2023-10-16 15:56 48阅读 0赞

#### 746. 使用最小花费爬楼梯 ####

*  题干描述
 *  解题思路
 *   *  1. 确定dp数组以及下标的含义
     *  2. 确定递推公式
     *  3. dp数组如何初始化
     *  4. 确定遍历顺序
     *  5. 举例推导dp数组
 *  代码实现

## 题干描述 ##

[力扣入口][Link 1]

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

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

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

示例1：  
![在这里插入图片描述][c72698276243420e900478220d77b677.png]  
![在这里插入图片描述][ae4732312fac401a8b6e296eea78e8f4.png]

## 解题思路 ##

跳到 下标 0 或者 下标 1 是不花费体力的， 从 下标 0 下标1 开始跳就要花费体力了。

### 1. 确定dp数组以及下标的含义 ###

使用动态规划，就要有一个数组来记录状态，本题只需要一个一维数组dp\[i\]就可以了。

**dp\[i\]的定义：到达第i台阶所花费的最少体力为dp\[i\]**。

**对于dp数组的定义，大家一定要清晰！**

### 2. 确定递推公式 ###

**可以有两个途径得到dp\[i\]，一个是dp\[i-1\] 一个是dp\[i-2\]。**

dp\[i - 1\] 跳到 dp\[i\] 需要花费 dp\[i - 1\] + cost\[i - 1\]。

dp\[i - 2\] 跳到 dp\[i\] 需要花费 dp\[i - 2\] + cost\[i - 2\]。

那么究竟是选从dp\[i - 1\]跳还是从dp\[i - 2\]跳呢？

一定是选最小的，所以dp\[i\] = min(dp\[i - 1\] + cost\[i - 1\], dp\[i - 2\] + cost\[i - 2\]);

### 3. dp数组如何初始化 ###

看一下递归公式，dp\[i\]由dp\[i - 1\]，dp\[i - 2\]推出，既然初始化所有的dp\[i\]是不可能的，那么只初始化dp\[0\]和dp\[1\]就够了，其他的最终都是dp\[0\]dp\[1\]推出。

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

所以初始化 dp\[0\] = 0，dp\[1\] = 0;

### 4. 确定遍历顺序 ###

最后一步，递归公式有了，初始化有了，如何遍历呢？

本题的遍历顺序其实比较简单，简单到很多同学都忽略了思考这一步直接就把代码写出来了。

因为是模拟台阶，而且dp\[i\]由dp\[i-1\]dp\[i-2\]推出，所以是从前到后遍历cost数组就可以了。

> 但是稍稍有点难度的动态规划，其遍历顺序并不容易确定下来。  
> 例如：01背包，都知道两个for循环，一个for遍历物品嵌套一个for遍历背包容量，那么为什么不是一个for遍历背包容量嵌套一个for遍历物品呢？  
> 以及在使用一维dp数组的时候遍历背包容量为什么要倒序呢？

### 5. 举例推导dp数组 ###

拿示例2：cost = \[1, 100, 1, 1, 1, 100, 1, 1, 100, 1\] ，来模拟一下dp数组的状态变化，如下：  
![在这里插入图片描述][42b08e4d87d34d9787d15fb1384b42e1.png]

## 代码实现 ##

class Solution {
        
       // 746. 使用最小花费爬楼梯
        public int minCostClimbingStairs(int[] cost){
        
            int len = cost.length;
            int[] dp = new int[len + 1];
    
            // 从下标为0或下标为1的台阶开始，因此支付费用为0
            dp[0] = 0;
            dp[1] = 0;
    
            // 计算机到达每一层台阶的最小费用
            for(int i = 2; i <= len; i++){
        
                dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i -2]);
            }
            return dp[len];
        }
    }

**参考资料**：[代码随想录-746. 使用最小花费爬楼梯][-746.]

[Link 1]: https://leetcode.cn/problems/min-cost-climbing-stairs/
[c72698276243420e900478220d77b677.png]: https://img-blog.csdnimg.cn/c72698276243420e900478220d77b677.png
[ae4732312fac401a8b6e296eea78e8f4.png]: https://img-blog.csdnimg.cn/ae4732312fac401a8b6e296eea78e8f4.png
[42b08e4d87d34d9787d15fb1384b42e1.png]: https://img-blog.csdnimg.cn/42b08e4d87d34d9787d15fb1384b42e1.png
[-746.]: https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE