Leetcode 746 使用最小花费爬楼梯

题意理解：

????????给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。

????????一旦你支付此费用，即可选择向上爬一个或者两个台阶。
????????你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯

? ? ? ? 目标：使用最小的花费到达楼梯顶部。

? ? ? ? 例：

? ? ? ? 爬到第零阶、第一阶的最小花费为0.因为可以选择第一阶或第零阶开始跳。

? ? ? ? 爬到第二阶的花费：

? ? ? ? ? ? ? ? 从第一阶爬一步，cost=15,爬至第二阶。

? ? ? ? ? ? ? ? 从第零阶爬两步，cost=10,爬至第二阶

? ? ? ? ? ? ? ? 则爬到第二阶的最小花费cost=10

? ? ? ? 爬到第三阶的花费：

? ? ? ? ? ? ? ? 从第二阶爬一步，cost=到第二阶最小花费+15=10+20=30

? ? ? ? ? ? ? ? 从第一阶爬两步,? ?cost=15

? ? ? ? ? ? ? ? 则爬到第三阶的最小花费cost=15

解题思路：

? ? ? ? 采用动态规划的题目进行分析：

? ? ? ? 1.根据题目dp[i]表示到达第i阶的最小花费。

? ? ? ? 2.递推公式：dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

? ? ? ? 3.初始化： dp[0]=0 dp[1]=0

? ? ? ? 4.确定遍历顺序：后面的状态总是由前面的状态确定，则遍历顺序总是从前往后的。

? ? ? ? 5.打印数组 ，可以用于debug验证思路。

1.动态规划解题

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;i++){
            //递推公式
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }

2.存储压缩

 public int minCostClimbingStairs(int[] cost) {
        //定义存储//初始化
        int min=0,dp0=0,dp1=0;
        if(cost.length==0||cost.length==1) return 0;
        //遍历
        for(int i=2;i<=cost.length;i++){
            //递推公式
            min=Math.min(dp1+cost[i-1],dp0+cost[i-2]);
            dp0=dp1;
            dp1=min;
        }
        return min;
    }

3.分析

时间复杂度：O(n) 用来遍历台阶的时间

空间复杂度：

? ? ? ? 数组存储：O(n)

? ? ? ? 数值存储：O(1)

n表示台阶数