LeetCode 70. Climbing Stairs

はじめに

LeetCode 「70. Climbing Stairs」の問題をGoで解きました。

問題

https://leetcode.com/problems/climbing-stairs/description/

問題文

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

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

和訳
階段を登っています。頂上までn段登る必要があります。
1回につき1段か2段登ることができます。頂上まで登るには、何通りの登り方がありますか？

例

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

Input: n = 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

制約

• 1 <= n <= 45

解答1 (動的計画法 Bottom-up)

n段の階段を登る方法の数 をより小さい問題に分解するのがポイントです。
階段の頂上にたどり着く最後の一歩は以下のどちらかです。

• 1段前から1段上がる
• 2段前から2段上がる

つまり、
n 段にたどり着く方法の総数 = n-1 段にたどり着く方法の総数 + n-2 段にたどり着く方法の総数
になります。

動的計画法(DP) の Bottom-up のアプローチだと解きやすいです。
最も単純な部分問題から解き始め解を保存し、それを利用してより大きな部分問題を解き、最終的に全体の答えに到達します。

0段目にたどり着く数dp[0], 1段目にたどり着く数dp[1]をそれぞれ初期化し、その値を利用しながら2段目以降を計算しています。

コード

func climbStairs(n int) int {
    if n <= 1 {
        return 1
    }
    dp := make([]int, n+1)
    dp[0] = 1
    dp[1] = 1

    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    
    return dp[n]
}

なお、この問題は、実質的にフィボナッチ数列と同じ漸化式になっています。

計算量

• 時間的計算量：O(n)
• 空間的計算量：O(n)

解答2(最適化)

解答1はnの数だけ配列が大きくなります。
直近の2つだけ覚えておけば解くことができるので、以下のように最適化が可能です。

コード

func climbStairs(n int) int {
    if n <= 1 {
        return 1
    }
    first, second := 1, 1
    for i := 2; i <= n; i++ {
        first, second = second, first+second
    }
    return second
}

first, second はそれぞれ「一つ前の段」「二つ前の段にたどり着く方法の数」です。

計算量

• 時間的計算量：O(n)
• 空間的計算量：O(1)