Description

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

好像网上讲动态规划经常举例的题目。

爬楼梯，可以一次爬一格或者两格，问有多少种不同的方式爬到顶。

Solution

与《63. Unique Paths II》非常相似。

到达第n格可以通过第n-1格爬一格和第n-2格爬两格，两种方式达到。

所以有：$$ f(n) = f(n-1) + f(n-2) $$

动态规划（Dynamic Programming）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func climbStairs(n int) int {
    steps := []int{0, 1, 2}
    if n <= 2 {
        return steps[n]
    }

    for i := 2; i < n; i++ {
        // tmp := steps[2]
        // steps[2] = steps[1] + steps[2]
        // steps[1] = tmp
        steps[1], steps[2] = steps[2], steps[1]+steps[2]
    }

    return steps[2]
}

递归（Recursive）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func climbStairs(n int) int {
    // f(n) = f(n-1) + f(n-2)
    // f(n-1) = f(n-2) + f(n-3)
    // 为了避免计算两次f(n-2) 增加缓存
    m := map[int]int{1: 1, 2: 2}

    var solve func(int) int
    solve = func(n int) int {
        if num, ok := m[n]; ok {
            return num
        }
        m[n] = solve(n-1) + solve(n-2)
        return m[n]
    }
    return solve(n)
}

Similar Problem