使用最小花费爬楼梯(java实现)

力扣 746 使用最小花费爬楼梯

题目说明

数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i] (索引从0开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例

例1

1
2
3

输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。

例2

1
2
3

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。

笔者理解

此题是一道走楼梯算法问题，在力扣题库中被定义为简单题。

解法

当笔者看见此题时，上台阶步骤可选择且为求最少消耗体力，笔者一下子就想到了动态规划法，就让我们看看具体如何实现吧。

public int minCostClimbingStairs(int[] cost) {
        int size = cost.length;
        int dp[] = new int[size];
        //定义一个动态规划数组用以存储到达每个台阶的最少消耗体力
        dp[0] = cost[0];
        //第一个台阶最少消耗
        dp[1] = cost[1];
        //第二个台阶最少消耗
        for(int i=2;i<size;i++){
            //依次求出剩下的台阶的可能
            dp[i] = Math.min(dp[i-2]+cost[i],dp[i-1]+cost[i]);
            //当前台阶的最小消耗
            //只可能由i-2台阶 或者 i-1台阶的最少消耗
            //加上到达当前台阶的消耗
        }
        return Math.min(dp[size-1],dp[size-2]);
        //返回倒数第一级台阶和倒数第二级台阶中的体力消耗较小者
    }