🍞题目描述
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例一：
示例二：
🥟算法原理（解法一）
步骤1：状态表示
步骤2：状态转移方程
现在我们进行题目的分析，我们知道dp[i]表示到达i位置需要的最小花费，其中到达i位置分为两种情况。我们先以i位置为结尾（以i位置为起点来进行分析是下面的解法二），根据最近的一步来进行题目的分析，总共分为两种情况。
步骤3：初始化
步骤4：填表顺序
步骤5：返回值
🍭算法原理（解法二）
刚刚我们是按照以i的位置为结尾进行思考分析，现在我们按照以i的位置为开头来进行思考分析。
好了，这里我们依然按照那5个步骤进行分析，请看：
步骤1：状态表示
步骤2：状态转移方程
步骤3：初始化
步骤4：填表顺序
步骤5：返回值
🍰代码实现（解法1）
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
//1.创建dp表
//2.初始化（防止越界）
//3.填表
//4.返回值
int n = cost.size();
vector<int> dp(n+1);
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];//下边n就是楼顶
}
};
🍡代码实现（解法2）
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
//1.创建dp表
//2.初始化
//3.填表
//4.返回值
int n = cost.size();
vector<int> dp(n);
dp[n-1]=cost[n-1],dp[n-2]=cost[n-2];
for(int i = n-3;i>=0;i--)
dp[i]=min(cost[i]+dp[i+1],cost[i]+dp[i+2]);
return min(dp[0],dp[1]);
}
};
🍋总结
利用i位置之前或者之后的状态来进行状态转移方程的推导，本文使用了两种方法来解决使用最小花费爬楼梯：
第一种思路：以i位置为结尾进行分析，dp[i]表示到达i位置所需要的最小花费。状态转移方程dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
第二种思路：以i位置为起点进行分析，dp[i]从i位置出发到达顶部所需要的最小花费。状态转移方程为dp[i]=min(cost[i]+dp[i+1],cost[i]+dp[i+2])。
好了，本文就到这里啦！
再见啦友友们！！！