LeetCode 题解：746. 使用最小花费爬楼梯

题目

点我查看详细原题

题目大意：

1. 数组的每个值对应为一个阶梯数
2. 每个阶梯数都对应一个体力花费数
3. 每爬一个阶梯就要消耗相应的体力
4. 可以选择一次爬一个或者一次爬两个（就是跳过一个阶梯，跳过的阶梯不算体力）
5. 找到到达目的地的最低体力花费数
6. 可以从 0 或 1 开始爬

示例 1:

1
2
3
4

输入: cost = [10, 15, 20]
输出: 15

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

示例 2:

1
2
3
4

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6

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

注意：

1. cost 的长度将会在 [2, 1000]。
2. 每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。

题目分析

动态规划思想

按结果分析，最终结果可以从倒数第一个到达和倒数第二个到达

1. 假设只有两个元素

此时的结果就是 cost[0] 和 cost[1] 中最小的那个

2. 假设只有三个元素分别为 1，2，3

   我们可以一眼看出最小的结果即为 2。仔细观察就会发现，我们取了爬到 2 和 3 元素的最小值，因为爬到 2 元素消耗为2，爬到 3 元素消耗为 3。

   1. 为何爬到 3 元素消耗为 3 呢

   因为我们选择了 1 元素为起始点，并且略过了 2 元素

   2. 爬到 3 元素的表达式怎么写?

   min(cost[0], cost[1]) + cost[3]

   3. 比较爬到 3 元素和 2 元素的消耗，不难得出最终登上楼梯的最小消耗为 2
   4. 根据动态规划思想写转移方程

   dp[0] = cost[0] 、dp[1] = cost[1]、dp[2] = min(dp[0] + dp[1]) + cost[2]

3. 将 3 个元素的转移方程推广到 n 个元素

dp[n] = min(dp[n-1] + dp[n-2]) + cost[n] 此时 n > 2

图解如下

仔细观察就会发现，我们取了跳到 2 和 3 元素的最小值，因为跳到 2 元素消耗为2，跳到 3 元素消耗为 3。

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

因为借用了 dp 数组，所以空间复杂度为 O(n)，此题也可以将 dp 数组修改为 两个变量从而实现空间复杂度为 O(1)的情况。