1.使用最小花费爬楼梯
题目连接:746. 使用最小花费爬楼梯
给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
2.题目解读
例如上面的例子,从下标为0的地方开始爬楼梯,向上爬一个或者两个台阶,最后到达顶部,输出6。其实两个问题,就是我怎么知道从0下标还是1下标开始?我怎么知道是要爬一个还是两个台阶?
3.解决问题(解法一)
(1)、状态表示
上面的问题1,我怎么知道从0下标还是1下标开始?只需要定义dp[i]为到达 i 位置时的最⼩花费即可。 如:dp[3]根据以往的计算这个就是最小花费,至于从0还是1下标,那就要问,dp[0]和dp[1]的最小花费是多少。
(2)、状态转移⽅程
根据以往的推出的结果(dp[i]之前或之后),来推导dp[i]。这里根据题目推导状态转移方程,即可解决知道是要爬一个还是两个台阶(最优即:最小花费)。
(3)、初始化
dp[0] = dp[1] = 0本来就可以在0或1下标。
(4)、初始化顺序
这里根据题目要求,根据状态转移方程,从左往右,将dp填充。
(5)、返回值
返回dp[n]即为,返回结果。
4.参考代码(解法一)
C++版本:
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {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];}
};
Java版本:
class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;int dp[] = new int[n + 1];for(int i = 2;i <= n;i++){dp[i] = Math.min(cost[i - 1] + dp[i - 1],cost[i - 2] + dp[i -2]);}return dp[n];}
}
5.解决问题(解法二)
(1)、状态表示
dp[i]表示到达楼梯顶部的最少花费。
(2)、状态转移⽅程
(3)、初始化
dp[n -1] = cost[n-1],dp[n-2] = cost[n-2]
(4)、初始化顺序
这里根据题目要求,根据状态转移方程,从右往左,将dp填充。
(5)、返回值
返回min(dp[0],dp[i])就是结果
6.参考代码(解法二)
C++版本:
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n + 1);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]);}
};