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表示台阶数