leetcode ：746使用最小花费爬楼梯
746. 使用最小花费爬楼梯
题目链接https://leetcode.cn/problems/min-cost-climbing-stairs/
题目描述
给定一个整数数组 cost，其中 cost[i] 是从楼梯第 i 个台阶爬到 i+1 个台阶的费用。每次你可以选择爬一个台阶或两个台阶。你需要支付一定的费用才能爬到楼梯的顶部，求使得总费用最小的方案。
你可以从下标为 0 或 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
示例 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 。
题目解法
我们根据描述可以观察到，到达第i个台阶的最优方案是从第i-1个台阶爬到第i个台阶，或者从第i-2个台阶爬到第i个台阶。因此，我们可以用动态规划来解决这个问题。
设dp[i]表示到达第i个台阶的最低花费，则有如下递推式：
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
即，如果从第i-1个台阶爬到第i个台阶的花费更低，则从第i-1个台阶爬到第i个台阶；否则，从第i-2个台阶爬到第i个台阶。
初始条件：
dp[0] = 0
dp[1] = 0
答案即为dp[n]，其中n为cost数组的长度。
我们可以省略数组，用两个变量left和right来代替，left表示从第i-2个台阶爬到第i个台阶的最低花费，right表示从第i-1个台阶爬到第i个台阶的最低花费。
则有如下递推式：
left = right
right = min(left + cost[i-2], right + cost[i-1])
即，如果从第i-2个台阶爬到第i个台阶的花费更低，则从第i-2个台阶爬到第i个台阶；否则，从第i-1个台阶爬到第i个台阶。
复杂度分析
时间复杂度：O(n)，其中n为cost数组的长度。
空间复杂度：O(1)。
代码实现
C++实现：
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();int left=0,right=0,next;for(int i=2;i<=n;i++){next=min(left+cost[i-2],right+cost[i-1]);left=right;right=next;}return right;}
};
GO实现：
func minCostClimbingStairs(cost []int) int {n := len(cost)pre, cur := 0, 0for i := 2; i <= n; i++ {pre, cur = cur, min(cur+cost[i-1], pre+cost[i-2])}return cur
}
python实现：
class Solution(object):def minCostClimbingStairs(self, cost):""":type cost: List[int]:rtype: int"""pre,cur=0,0n=len(cost)for i in range(2,n+1):pre,cur=cur,min(pre+cost[i-2],cur+cost[i-1])return cur