最小花费爬楼梯

从[0, n]共有n+1个楼梯。前n个楼梯对应的有各自的花费cost[i]。终点位置是第n个楼梯。

• 当终点位置n = 1时，可以直接从1楼梯出发直接到达终点1，故花费为0；

• 当终点位置n >= 2时，无论从0还是1楼梯出发，都得花费cost进行爬楼梯，利用dp数组记录结果。

import java.util.*;


public 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(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }

        return dp[n];
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] costs) {
        // write code here
        // 算法核心：从【递归回溯尝试】优化到【记忆化搜素】（因为装填转移只有2个，因此效率与动态规划类似）
        // dp表默认初始化全-1
        int[] dp = new int[costs.length + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = -1;
        }
        // 注意，爬到数组刚好越界才算爬完
        int result = process(costs, costs.length, dp);
        return result;
    }

    // 计算爬到第target阶（0开始）的最小花费
    public int process (int[] costs, int target, int[] dp) {
        // 递归出口
        if (target == 0) {
            // 爬到第0阶台阶的最小花费
            // 为0，因为可以直接从0开始爬
            dp[0] = 0;
            return dp[0];
        }
        if (target == 1) {
            // 爬到第1阶台阶的最小花费
            // 为0，因为可以直接从1开始爬
            dp[1] = 0;
            return dp[1];
        }

        // 分支尝试

        // 本题状态的转移是【有限个】的，即【不依赖for循环】列举进行状态转移
        // 因此，【记忆化搜索】与【经典动态规划】的时间复杂度【近似】

        // 如果dp表中有计算好的值，则可直接返回
        if (dp[target] != -1) {
            return dp[target];
        }
        // 上了一个台阶到达target位置
        if (dp[target - 1] == -1) {
            // dp表中无值
            dp[target - 1] = process(costs, target - 1, dp);
        }
        int one = dp[target - 1] + costs[target - 1];
        
        // 上了两个台阶到达target位置
        if (dp[target - 2] == -1) {
            // dp表中无值
            dp[target - 2] = process(costs, target - 2, dp);
        }
        int two = dp[target - 2] + costs[target - 2];

        // 记录本位置dp值
        dp[target] = Math.min(one, two);
        return dp[target];
    }
}

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];
    }

public class Solution {
    public int minCostClimbingStairs (int[] cost) {
        // 爬到第i级楼梯所需的最小花销
        int[] dp = new int[cost.length + 1];
        // 可以选择从0或者1开始
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= cost.length; 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);
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        //dp[n]=min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2])，爬到第n层的最低花费
        //dp[1]=dp[0]+cost[0]/0
        //dp[2]=dp[1]+cost[1]/dp[0]+cost[0]
        int a = 0,b = 0,c = 0;
        for(int i = 2;i<=cost.length;i++){
            c = Math.min(a+cost[i-2],b+cost[i-1]);
            a = b;
            b = c;
        }
        return c;
    }
}

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;
    }
}

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

import java.util.*;


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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
   
    public   int minCostClimbingStairs(int[] cost) {
        //方法:要使得f(n)最小则,到达n需要从n-1或者n-2跳过来,则需要取跳到n-1或者n-2的最小花费拿出来

        //设n层最小花费f(n),n-1层为f(n-1)  n-2层为f(n-2)   而从n-1跳到n的花费为cost[n-1],从n-2跳到n的花费为cost[n-2],

        //即:f(n) = Math.min(f(n-1)+cost[n-1],f(n-2)+cost[n-1])   f(0)=f(1) = 0


         int length = cost.length;//楼层个数
        
        int [] minmoney = new int[length+1];//因为最后一层必须跨过去,所以长度+1

        //0位和1位不需要花费,二开始即minmoney[0]=0=minmoney[1],如果长度大于2,则0位和1位默认0
        for (int i = 2; i <= length; i++) {
            minmoney[i] = Math.min(minmoney[i-1]+cost[i-1],minmoney[i-2]+cost[i-2]);
        }

        return minmoney[length];
    }

}

应该挺好理解的，我也不多说什么了。我第一遍写的时候，用的是，递归写的，之后因为超时了，想到要把前面求过的存起来，因为用递归的话，有的值会求很多遍。另外，由于要的结果是顶层的路费。最后到达顶层的时候，是不需要再加路费的，所以我把顶层的那一步留了出来。

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

import java.util.*;


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

import java.util.*;


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

定义dp[i]表示为跳到第i个台阶的最小花费（第i个台阶的花费不计算在内）；
最终，返回值应该为dp[n]；
起跳点为0或者1，那么对应的base case为：
dp[0] = 0, dp[1] = 0; // 表示跳到0、1位置需要总花费0的代价；
因为青蛙每次有两种选择，分别为1步和两步，那么dp[i] 有两种可能：

1. 一种从i-1位置起跳，跳一步到达i位置；此时最小花费 dp[i-1] + cost[i-1] (从i-1位置起跳的话，要收这个台阶的过路费）；
2. 另外一种从i-2位置起跳，跳两步到达i位置；此时最小花费 dp[i-2] + cost[i-2](从i-2位置起跳的话，也要收过路费的）

综上，我们要求的是dp[i]表示到达i位置的最小花费，所以 dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        // dp[i] 表示 跳到i这个台阶的最低花费；
        int n = cost.length;
        int[] dp = new int[n+1]; // 返回值 为 dp[n]
        dp[0] = 0; dp[1] = 0;

        for (int i = 2; i<= n; i++) {
            dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[n];
    }
}```