LeetCode
September 3, 2018

Min Cost Climbing Stairs

Min Cost Climbing Stairs

题目

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

1
2
3
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:

1
2
3
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

思路分析

其实，刚看到这个题目的时候，我是有点迷惑的，甚至浪费了不少时间。

比如对于第一个例子，我以为结果应该是10。因为我从第0个台阶开始，跨两步就可以到达最顶层。

然而，这样的理解和题目的本意是不相符的。题目中的“top of the floor”只的是最后一层台阶的更上一层。也就是说，对于第一个例子，我需要跨到3层（从0开始）台阶上去。如果从第0个台阶开始的话，花费是（10+20）= 30，而如果从第1个台阶开始，直接跨两步的话，则花费是15。

理解了题目含义，我们开始做题。很显然，这是一道动态规划问题。

而且我们有如下递归公式：

$$
\left{
\begin{array}{lr}
\mathrm{dp}[0] = \mathrm{cost}[0] & \
\mathrm{dp}[1] = \mathrm{cost}[1] & \
\mathrm{dp}[i] = \mathrm{cost}[i] + \mathrm{min}(\mathrm{dp}[i-1], \mathrm{dp}[i-2]) &
\end{array}
\right.
$$

从第2层开始，我们往上走的选择是保持当前的花费最小，从而我们从前面的花费中选择最小的和当前的楼层的$\mathrm{cost}[i]$相加。最后的返回值应该是$\mathrm{min}(\mathrm{dp}[i], \mathrm{dp}[i-1])$。这种思路是一种正向思考。

这是一种思路，其实我们还有另外一种思路。

$$
\left{
\begin{array}{lr}
\mathrm{dp}[0] = 0 & \
\mathrm{dp}[1] = 0 & \
\mathrm{dp}[i] = \mathrm{min}(\mathrm{cost}[i - 1] + \mathrm{dp}[i-1], \mathrm{cost}[i - 2] + \mathrm{dp}[i-2]) &
\end{array}
\right.
$$
因为从2开始，第$i$层的花费可以由通过$i-2$层走2层或者通过$i-1$走1层到达，而$i-2$和$i-1$层所要花费的值分别为cost[$i-2$]和cost[$i-1$]。最后的返回值应该是$\mathrm{dp}[i]$。这种思路是一种反向思考，假设我们已经到达了顶点，然后列出我们达到顶点之前的两种可能选择。

C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int minCostClimbingStairs(vector<int> &cost) {
    // 第二种思路
    int dp0 = 0;
    int dp1 = 0;
    int dp = 0;
    for (int i = 2; i <= cost.size(); i++) {
        dp = min(dp0 + cost[i - 2], dp1 + cost[i -1]);
        dp0 = dp1;
        dp1 = dp;
    }
    return dp;
    /* 第一种思路
    int dp0 = cost[0];
    int dp1 = cost[1];
    int dp = 0;
    for (int i = 2; i < cost.size(); i++) {
        dp = cost[i] +  min(dp0, dp1);
        dp0 = dp1;
        dp1 = dp;
    }
    return min(dp0, dp1);
    */
}

int main() {
    unsigned int n = 0;
    cout << "请输入楼梯层数：\n";
    cin >> n;
    vector<int> cost(n);
    cout << "请输入每层的权值：\n";
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    int result = minCostClimbingStairs(cost);
    cout << result << endl;
    return 0;
}

Scala实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package leetcode

import scala.math._
import scala.io.StdIn

object MinCostClimbingStairs {
  def minCostClimbingStairs(cost: Array[Int]): Int = {
    val dp = cost.clone
    for (i <- 2 until cost.length) {
      dp(i) = cost(i) + min(dp(i - 1), dp(i -2))
    }
    return min(dp(dp.length - 1), dp(dp.length - 2))
  }

  def main(args: Array[String]): Unit = {
    println("请输入楼梯层数：")
    val count = StdIn.readInt()
    val cost = Array.fill[Int](count)(0)
    println("请输入每层的权值：")
    for (i <- 0 until cost.length) {
      cost(i) = StdIn.readInt()
    }

    println(minCostClimbingStairs(cost))
  }

}