Zenn
😆

LeetCode 70. Climbing Stairs

2021/12/04に公開
Kotlin
LeetCode
tech

Question

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段あるいは2段で登れるとき、何種類登れる方法があるかという問題

Code

class Solution {
    fun climbStairs(n: Int): Int {
        if (n < 3) return n

        var array = Array<Int>(n + 1) { if (it < 3) it else 0 }

        for (i in 3..n) {
            array[i] = array[i - 1] + array[i - 2]
        }

        return array[n]
    }
}

  • サンプルから分かる情報として

    • n=1のとき、1pattern({1,1})
    • n=2のとき、2pattern({1,1},{2})

  • n=3のとき、3pattern({1,1,1},{2,1},{1,2})

  • n=4のとき、5pattern({1,1,1,1},{2,1,1},{1,2,1},{1,1,2},{2,2})

  • n=5のとき、8pattern({1,1,1,1,1},{2,1,1,1},{1,2,1,1},{1,1,2,1},{2,2,1},{1,1,1,2},{2,1,2},{1,2,2})

  • これらを表にまとめると以下である。

n(段) 1 2 3 4 5
pattern 1 2 3 5 8

選択肢が1段あるいは2段であるから、n-1段までとn-2段目までの行き方の合計がn段目までの行き方の合計であることがわかる。つまりn=0,1,2のときのルールが異なるフィボナッチ数列として解けば良いが、

class Solution {
    fun climbStairs(n: Int): Int {
        if (n == 1) return 1
        if (n == 2) return 2
        return climbStairs(n - 1) + climbStairs(n - 2)
    }
}

のように、定義通りに求めると、climbStairsの呼び出し毎に、一度計算した式を遡って再度計算を行うため、時間計算量がO(n^2)となってしまう問題や、nの値が大きいほど、メモリが足りなくなり、スタックオーバーフローが発生する問題を抱えている。

そこで採ったのが1つ前、2つ前の計算結果を記録しておき、ボトムアップで計算していけば、O(n)で解けるというものだ。

さらに行列計算を用いれば、O(log n)で解けるようだが、それはまた別の機会としたい。

Profile

  • Runtime: 120 ms
  • Memory Usage: 33 MB

Submission

GitHubで編集を提案

Discussion