# LeetCode Easy 70. Climbing Stairs

tags: leetcode

問題

• Explore
• Problems

あなたは階段を上がっている. 最上段へたどり着くのに$n$段が必要である.

毎回あなたは$1$段もしくは$2$段上がることができる. 異なる方法で何回最上段まで上がることができるか?

注意

与えられる$n$は正の整数である.

解法1(recursive)

再帰的な構造を考えると最初に思いつくのは再帰関数を用いた解き方です

答えとして出力する変数ansを宣言します(初期値は$0$)

• 基底は$n$段以上に登ったとき
  • $n$段ちょうどのときは1つの登り方が見つかったということなのでansをインクリメントします
  • それ以上登ってしまったときは関数を終了させます
• 基底以外は$n$段駆け上がったということなので

計算量

• 空間計算量
  • 登る際に$1$段登るか$2$登るか選択肢が$2$つあります
  • そのため$O(n)$です
• 時間計算量
  • 空間計算量は再帰呼出しの深さに依存するので$O(n)$です

Python

PythonだとTLEします

class Solution:
    def climbStairs(self, n: int) -> int:
      self.ans = 0
      def helper(steps):
        if steps == n:
          self.ans += 1
        elif steps > n:
          return
        else:
          helper(steps + 1)
          helper(steps + 2)
      helper(0)
      return self.ans

C++

C++でもTLEになります...

つまりもっと効率的な計算方法があるということです

class Solution {
public:
  int climbStairs(int n) {
    int ans = 0;
    helper(n, 0, ans);
    return ans;
  }
private:
  void helper(int& maxSteps, int steps, int& ans) {
    if (steps == maxSteps) {
      ++ans;
    } else if (steps > maxSteps) {
      return;
    } else {
      helper(maxSteps, steps+1, ans);
      helper(maxSteps, steps+2, ans);
    }
  }
};

解法2(memoization)

上のアルゴリズムではC++でもTLE(タイムオーバー)になってしまいます

次は再帰的なアルゴリズムで共通する部分に注目します

上のアルゴリズムでは同じ関数を何回も呼んでいます!(紙に書いてみて下さい)

それを効率化するにはメモ化(memoization)という手法を使います

これは配列に関数を実行した結果を記録して, それを再利用するという手法です

• $n$段目まで登ることを配列の$n-1$目の要素に記録します
• $1$段目まで登る方法は$1$通り, $2$段目まで登る方法は$2$通りなのでそのように配列を初期化します
• これより上の段について考えます
  • $n$段目に上がるには$n-1$段目から行く方法が$1$通り, $n-2$段目から行く方法が$2$通りあります
• これを実装すれば良いです

計算量

• 空間計算量
  • 配列の長さは$n$なので$O(n)$
• 時間計算量
  • 時間計算量は以前計算した要素から計算した新しい配列の要素にするので$O(n)$

Python

class Solution:
    def climbStairs(self, n: int) -> int:
      if n <= 2:
        return n
      ans = [1, 2]
      for _ in range(n - 2):
        ans.append(ans[-2] + ans[-1])
      return ans[-1]

C++

class Solution {
public:
  int climbStairs(int n) {
    vector<int> ans{1, 2};
    for (int i = 0; i < n - 2; i++) {
      ans.push_back(ans[i] + ans[i+1]);
    }
    return ans[n-1];
  }
};