最小花费爬楼梯

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        if(cost.length == 1) return cost[0];
        
        // 初始化两个变量， dp1 = 下标为0的台阶，需要花费， dp2 = 下标为1的台阶，需要花费
        int dp1 = cost[0], dp2 = cost[1];
        
        // 遍历cost数组，从下标2开始
        for (int i = 2; i < cost.length; i++) {
            // 暂存dp2，因为dp1和dp2的花费需要向后移动，所以dp1的花费需要切换到 dp2
            int temp = dp2;
            // 将当前i层台阶的花费 + dp1花费， 与  当前i层台阶的花费 + dp2花费 取最小花费值 赋给dp2
            // 即当达到下标为i层台阶的时候，花费为 (当前i层台阶的花费 + dp1花费， 与  当前i层台阶的花费 + dp2花费 取最小花费值)
            dp2 = Math.min(cost[i] + dp1, cost[i] + dp2);
            // 然后dp1的花费后移，改为之前的dp2
            dp1 = temp;
        }
        // 循环结束时，对比dp1 和 dp2的花费 取最小值
        return dp1 > dp2 ? dp2 : dp1;
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型vector 
     * @return int整型
     */
    int minCostClimbingStairs(vector<int>& cost) {
        // 时间复杂度O(N)，空间复杂度O(1)
        int dp0 = 0, dp1 = 0, dp2;
        for (int i = 2; i <= cost.size(); ++i) {
            dp2 = min(dp0 + cost[i - 2], dp1 + cost[i - 1]);
            dp0 = dp1;
            dp1 = dp2;
        }
        return dp2;
    }
};

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        // write code here
        if (cost.length == 1) return cost[0];
        int first=cost[0],second=cost[1];
        for (int i=2;i<cost.length;i++)
        {
            int temp=second;
            second=Math.min(first+cost[i],second+cost[i]);
            first=temp;
        }
        return first < second ? first : second;
    }
}

# 解法一
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # 初始化一个dp数组，数组的值为走到这一步所需的花费，数组的长度为n+1，因为最终要走出去
        dp = [0] * (n + 1)
        # 从第一步开始走，所以dp[0]和dp[1]都为0，因为不需要花费，所以从第二步开始，所以从下标2开始遍历，到n+1结束
        for i in range(2, n + 1):
            # 当前花费为（从上一步走来的花费加上之前的花费）或者（从上上一步走来的花费加上之前的花费），取最小值
            dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2])

        return dp[-1]


# 解法二
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # 初始化一个dp数组，数组的值为走到这一步所需的再加上走出这一步所需的总花费
        dp = [0] * n

        dp[0:2] = cost[0:2]

        for i in range(2, n):
            dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])

        # 最后一步可以选择从倒数第一步走出去，或者从倒数第二步走出去，取最小值
        return min(dp[-1], dp[-2])

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型vector 
     * @return int整型
     */
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int>dp(cost.size()+1); // dp[i]到达i台阶的 最小费用
        dp[0]=0;  //到达 0 和 1 都不需要花费 都是 0 ；
        dp[1]=0;
        for(int i=2;i<=cost.size();i++)
        {
             //到达i有两种方式 每种方式都是 到达自己的最小费用 + 从自己出发的费用
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.size()];
    }
};

public int minCostClimbingStairs (int[] cost) {
        if(cost.length == 1) return cost[0];
        if(cost.length == 2) return Math.min(cost[0],cost[1]);
        int a,b=cost[1],c = cost[0];
        for(int i=2;i<cost.length;i++){
            a = Math.min(cost[i]+b,cost[i]+c);
            c = b;
            b = a;
        }
        return Math.min(b,c);
    }

public int minCostClimbingStairs (int[] cost) {
        int[] dp=new int[cost.length+1];
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<cost.length+1;i++){
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }

import java.util.*;

public class Solution {
    public int minCostClimbingStairs (int[] cost) {
        int n = cost.length;
        if (n <= 1) return cost[0];
        int a = cost[0], b = cost[1], c = 0;
        for (int i = 2; i < n; i++) {
            c = Math.min(a, b) + cost[i];
            a = b;
            b = c;
        }
        return Math.min(a, b);
    }
}

vector<int> dp(cost.size() + 1);
for(int i = 2; i <= cost.size(); ++i)
    dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
return dp[cost.size()];

func minCostClimbingStairs( cost []int ) int {
    // write code here
    dp:=make([]int,len(cost))
    dp[0],dp[1]=cost[0],cost[1]
    for i:=2;i<len(cost);i++{
       dp[i]=min(dp[i-1],dp[i-2])+cost[i]
    }
    return min(dp[len(cost)-1],dp[len(cost)-2])
}
func min(a,b int)int{
    if a>b{
        return b
    }else{
        return a
    }
}

public int minCostClimbingStairs (int[] cost) {
        int[] dp = new int[cost.length];
        dp[dp.length - 1] = cost[dp.length - 1];
        dp[dp.length - 2] = Math.min(cost[dp.length - 2], cost[dp.length - 2] + cost[dp.length - 1]);
        for (int i = dp.length - 3; i >= 0; i--) {
            dp[i]=cost[i]+Math.min(dp[i+1],dp[i+2]);
        }
        return Math.min(dp[0],dp[1]);
    }

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    func minCostClimbingStairs ( _ cost: [Int]) -> Int {
        //思路：使用dp数组存储最小数，每次移动数组时， 比较i-1和i-2的大小
        var dp = [Int]()
        //因为0和1不需要花费钱，所以dp[0]和dp[1]为0
        dp.append(0)
        dp.append(0)
        //开始爬楼：楼顶为cost.count+1
        for i in 2...cost.count {
            let m = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
            dp.append(m)
        }
        return dp.last! //返回楼顶的花费
    }
}