本文主要是介绍leetcode746.使用最小花费爬楼梯（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例一：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 示例二：
输入：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.状态表示：
因为要使用动态规划来解决，所以必须要有dp数组来记录一个状态。
这道题中dp[i]表示到达i位置的最小花费，下面就要用前面的dp值以及cost值来表示dp[i]
2.状态转移方程
主要是通过之前的状态，来表示dp[i]的值。
因为题干中规定可以选择向上爬一个台阶或者两个台阶，对应dp[i]就要找出这两种情况下花费最小
的从而赋值给dp[i]。
dp[i]可以选择前一个台阶即[i - 1]的位置然后向上走一步，这时的花费为dp[i - 1] + cost[i - 1],对应的
为走一步的情况。
dp[i]可以选择前两个台阶即[i - 2]的位置然后向前走两步，这是的花费位dp[i - 2] + cost[i - 2],对应为
向前走两步的情况。
所以dp[i]的状态转移方程为：min(dp[i - 1] + cost[i - 1] , dp[i - 2] + cost[i - 2]).
3.初始化一些值
这一步主要是为了在填写dp表的时候不越界。
从状态转移方程中我们可以看到，使用了dp[i - 1]和dp[i - 2]这两个值，这也就意味着
我们需要初始化dp[0]和dp[1]这两个位置，那么应该初始化成什么呢？
因为题干中说可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯，所以这也就代表了前往第0个梯
子和第一个梯子不需要任何花费，所以初始化：
dp[0] = dp[i] = 0;
4.填表的顺序
应为dp[i]的实现依靠于dp[i - 1]和dp[i - 2]所以也就注定了顺序是从左向右的。
5.返回值
题干要求返回到达楼顶的最高位置，所以直接返回最高位置的dp数组的值就可以了。
细节：
到底哪里才算爬到楼顶，应该是将最后一个阶梯走完之后，才算爬到楼顶，所以也就注定了dp数组
的长度比cost数组的长度要多一位，用来记录最后到楼顶的花费。
对应的代码：
int minCostClimbingStairs(vector<int>& cost)
{// dp[i] 表示到达i位置的最小花费int n = cost.size();vector<int> dp(n + 1);dp[0] = 0;dp[1] = 0;for (int i = 2; i <= n; i++) {dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[n];
}动态规划的代码的书写方式很固定，首先判断是否有特殊情况，有的话直接先进行判断，然后
1.创建dp表
2.初始化dp中的一些元素
3.顺序填表（状态转移方程）
4.返回
方法二：
1.状态表示：
因为要使用动态规划来解决，所以必须要有dp数组来记录一个状态。
这道题中dp[i]表示从i位置出发，到达楼顶的最小花费
2.状态转移方程
主要是通过之后的状态，来表示dp[i]的值。
这里的dp[i]有了不同的含义，因为题干中规定可以向前走一步或者两步，所以可以选择后一个或者
后两个来取出最小的花费
dp[i]如果选择后一个台阶来进行跳跃，就需要从后一个位置出发，到达楼顶的最小花费来加上自己
位置本身的花费来表示dp[i]的值。
dp[i]如果选择后两个台阶来进行跳跃，就需要从后两个位置出发，到达楼顶的最小花费来加上自己
位置本身的画法来表示dp[i]的值。
所以dp[i]的状态转移方程是：dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]).
3.初始化一些值
这一步主要是为了在填写dp表的时候不越界。
观察状态转移方程发现需要dp的后两个位置的值，这也就意味着我们要初始化
dp[n - 1]和dp[n - 2]这两个值，那么这两个值应该初始化成什么呢？
由题干可知：可选择向上爬一个或者两个台阶，所以只要这两个台阶的人支付自己所在的台阶的费
用，就可以实现到达顶端。
对dp[n - 1]和dp[n - 2]的初始化为：
dp[n - 1] = cost[n - 1],dp[n - 2] = cost[n - 2].
4.填表的顺序
可以从状态转移方程看出，填表顺序是从右到左的
5.返回值
应为题干规定可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯
所以dp[0]和dp[1]都有可能是最终的答案，谁小取谁
min(dp[0],dp[]1)
最终的代码如下：
class Solution
{
public:int minCostClimbingStairs(vector<int>& cost) {// dp[i]表示从i位置出发，到达楼顶的最小花费//1.创建dp表int n = cost.size();vector<int> dp(n);//2.初始化dp中的一些元素dp[n - 1] = cost[n - 1];dp[n - 2] = cost[n - 2];//3.顺序填表（状态转移方程）for (int i = n - 3; i >= 0; i--) {dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);}//4.返回return min(dp[0], dp[1]);}
};这就是这道题的两种解法。
这篇关于leetcode746.使用最小花费爬楼梯（动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
