概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインでだそうです。
その対策としてLeetCodeなるサイトで対策を行うようです。
※LeetCodeとは
本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトです。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていきます。
問題
n段の階段を登り、頂上まで到達したい。
各段では、1段または2段登ることができる。
頂上まで登る方法は何通りあるか計算する問題。
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1 1 step + 1 step
2 2 steps
Example 2:
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
Constraints:
・1 <= n <= 45
解答
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1: return 1
fib = [0] * (n + 1)
fib[1] = 1
fib[2] = 2
for i in range(3, n + 1):
fib[i] = fib[i-1] + fib[i-2]
return fib[n]
解説
if n == 1: return 1
1段の場合、登り方は1通り。
fib = [0] * (n + 1)
段数に応じて計算結果をメモしておく配列。
※フィボナッチ数列と同じ性質をもっているためfibにしている。
インデックス0からnまでの要素数を確保。
fib[1] = 1、fib[2] = 2
事前に分かっている2段目までの結果をセット。
for i in range(3, n + 1):
3段目からn段目まで順に計算結果を埋めていくループ。
fib[i] = fib[i-1] + fib[i-2]
i段の階段を上る方法の数を埋めていく。
前の計算結果を用いて、次の計算結果を導き出している。
例
Input: n = 5
| i | fib[i] = fib[i-1] + fib[i-2] |
|---|---|
| 3 | fib[3] = fib[2] + fib[1] = 2 + 1 = 3 通り |
| 4 | fib[4] = fib[3] + fib[2] = 3 + 2 = 5 通り |
| 5 | fib[5] = fib[4] + fib[3] = 5 + 3 = 8 通り |
return fib[n] → 8
別解
フィボナッチ数列の一般項であるビネの公式を用いて、別解を作成してみた。
import math
class Solution:
def climbStairs(self, n: int) -> int:
a = (1 + math.sqrt(5)) / 2
b = (1 - math.sqrt(5)) / 2
result = (a**(n + 1) - b**(n + 1)) / math.sqrt(5)
return round(result)
Discussion