Leetcode刷题详解——使用最小花费爬楼梯

Leetcode刷题详解——使用最小花费爬楼梯
1. 题目链接：746. 使用最小花费爬楼梯

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

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

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

示例 1：
```
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
1
2
3
4
5
```
示例 2：
```
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
1
2
3
4
5
6
7
8
9
10
```
提示：
- 2 <= cost.length <= 1000
- 0 <= cost[i] <= 999
3. 解法1（动态规划）

3.1 算法思路：
1. 以i位置为结尾
dp[i]表示到达i位置时的最小花费（注意：到达i位置的时候，i位置的钱不需要算上）
1. 状态转移方程：
根据最近的一步，分情况讨论：

先到达i-1的位置，然后支付cost[i-1]，接下来走一步到i位置：dp[i-1]+cost[i-1]

先到达i-2的位置，然后支付cost[i-2]，接下来走两步到i位置：dp[i-2]+cost[i-2]
1. 初始化：
从我们的递推公式可以看出，我们需要先初始化i=0，以及i=1的位置的值。容易得到dp[0]=dp[1]=0，因为不需要任何花费，就可以直接站到0层和第1层上
1. 填表顺序：
  
  根据状态转移方程可得，遍历的顺序是从左往右
2. 返回值
  
  根据状态表示以及题目要求，需要返回dp[n]位置的值
3.2 C++算法代码：
```
class Solution {
public:
    int minCostClimbingStairs(vector& cost) {
        int n=cost.size();
        //创建一个pd表
        vectordp(n+1,0);
        //初始化
        dp[0]=dp[1]=0;
        //填表
        for(int i=2;i
```
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
4. 解法2（动态规划）

4.1 算法思路：
1. 状态表示：
以i位置为起点

dp[i]表示：从i位置出发，到达楼顶，此时的最小花费
1. 状态转移方程：
根据最近的一步，分情况讨论：

支付cost[i]，往后走一步，接下来从i+1的位置出发到终点：dp[i+1]+cost[i]

支付cost[i]，往后走两步，接下来从i+2的位置出发到终点：dp[i+2]+cost[i]

我们要的是最小花费，因此dp[i]=min(dp[i+1]，dp[i+2])+cost[i]
1. 初始化
为了保证填表的时候不越界，我们需要初始化最后两个位置，结合状态表示易得：dp[n-1]=cost[n-1]，dp[n-2]=cost[n-2]
1. 填表顺序
根据状态转移方程可得，遍历的顺序是从左往右
1. 返回值
2. 根据状态表示以及题目要求，需要返回dp[n]位置的值
4.2 C++算法代码：
```
class Solution {
public:
    int minCostClimbingStairs(vector& cost) {
        int n=cost.size();
        //创建dp表
        vectordp(n);
        //初始化
        dp[n-1]=cost[n-1],dp[n-2]=cost[n-2];
        //填表顺序
        for(int i=n-3;i>=0;i--)
        {
            dp[i]=min(dp[i+1],dp[i+2])+cost[i];
        }
        //返回值
        return min(dp[0],dp[1]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
```

相关阅读:
Nodejs安装及快速入门
每日一题~二叉搜索树中的插入操作
Spring MVC快速入门。
【LeetCode】每日一题：使二叉树所有路径值相等的最小代价
一周速学SQL Server（第四天）
【大数据 - Doris 实践】数据表的基本使用（二）：数据划分
软件配置管理计划
【Spring Cloud】新闻头条微服务项目：分布式文件系统MinIO实现文章页面存取
Jetson查看JetPack版本(tool)
XSS-labs（1-10）闯关详解

原文地址：https://blog.csdn.net/weixin_51799303/article/details/134074229

1. 题目链接：746. 使用最小花费爬楼梯

2. 题目描述：

3. 解法1（动态规划）

3.1 算法思路：

3.2 C++算法代码：

4. 解法2（动态规划）

4.1 算法思路：

4.2 C++算法代码：