746. 使用最小花费爬楼梯

1、题目描述

 2、题目解析

本题使用动态规划来解决比较简便，难点在于找到对应的递推公式。

根据题意分析，假设数组 cost 的长度为 n，则 n 个阶梯分别对应下标 0 到 n-1，楼层顶部对应下标 n，问题等价于计算达到下标 n 的最小花费。

• 创建长度为 n+1 的数组 dp，其中 dp[i] 表示达到下标 i 的最小花费。
• 由于可以选择下标 0 或 1 作为初始阶梯，因此有 dp[0]=dp[1]=0。

• 当 2≤i≤n 时，可以从下标 i−1 使用 cost[i−1] 的花费达到下标 i，或者从下标 i−2 使用 cost[i−2] 的花费达到下标 i。为了使总花费最小，dp[i] 应取上述两项最小值，因此状态转移方程如下：
  dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2]) 

  依次计算 dp 中的每一项的值，最终得到的 dp[n] 即为达到楼层顶部的最小花费。

因此根据上面的分析，实现代码如下：

class Solution {
      public int minCostClimbingStairs(int[] cost) {
          int n = cost.length;
          int[] dp = new int[cost.length+1];
          //进行初始化
          dp[0] = dp[1] = 0;
          for(int i=2; i < n+1 ; i++){
                dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) ;
          }
          return  dp[n];  
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组cost 的长度。需要依次计算每个 dp 值，每个值的计算需要常数时间，因此总时间复杂度是 O(n)。

空间复杂度：O(n)。使用了dp辅助空间，空间复杂度为辅助空间的大小n.

上面的代码可以进行进一步优化，注意到当 i ≥ 2 时，dp[i] 只和 dp[i−1] 与 dp[i−2] 有关，因此可以使用滚动数组的思想，将空间复杂度优化到 O(1)。

因此优化后的代码如下：

class Solution {
      public int minCostClimbingStairs(int[] cost) {
          int pre = 0; int cur = 0;
          for(int i = 2; i < cost.length+1; i++){
                int next = Math.min(pre+cost[i-2],cur+cost[i-1]);
                pre = cur;
                cur = next;
          }
          return cur;
      }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组cost 的长度。需要依次计算每个 dp 值，每个值的计算需要常数时间，因此总时间复杂度是 O(n)。

空间复杂度：O(1)。使用【滚动数组】的思想，只需要使用有限的额外空间。

备注：后面的解法就是基于dp动态规划的空间优化逻辑，得非常了解求解过程，否则，for循环的i的取值范围都不好判定，for(int i = 2; i < cost.length+1; i++)，  i < cost.length+1 才能到达cost.length的长度位置。