こちらは「Climbing Stairs」のPythonによる解答例となっております。この問題は、階段を1歩または2歩で上る方法の総数を求める問題です。
問題
整数 n が与えられたとき、階段を1歩または2歩で上る方法の総数を求めます。制約条件は以下の通りです。
- 1 <= n <= 45
解法
この問題は、動的計画法（DP）を用いた1つのアプローチがあります。DPを用いることで、再帰的に問題を解くことができます。
アルゴリズムの概要を以下に述べます。
- メモ化用の配列
dpを初期化します。 - 関数
DynamicProgrammingを定義します。この関数では、再帰的にDPを解いていきます。 - 関数
climbStairs内で、DynamicProgramming(n)を呼び出して、答えを求めます。
Pythonコード
以下のコードが、「Climbing Stairs」を解くためのPythonプログラムとなります。
### Function ##################################################################
def solve(num=0):
solver = Solution().climbStairs
if 1 <= num <= Input().input: id_LIST = [num]
else: id_LIST = [id+1 for id in range(Input().input)]
for id in id_LIST:
data = Input(id)
ans = solver(data.n)
result = "OK" if ans==data.ans else "NG"
print(f"[{str(id).zfill(3)}] {result}")
### Class #####################################################################
class Solution(object):
### DP Bottom to Top
# def climbStairs(self, n):
# """
# :type n: int
# :rtype: int
# """
# dp = [-1] * (n + 1)
# dp[0] = 1
#
# for i in range(1, n + 1):
# root_1 = dp[i - 1] if i - 1 >= 0 else 0
# root_2 = dp[i - 2] if i - 2 >= 0 else 0
# dp[i] = root_1 + root_2
#
# return dp[n]
### DP Top to Bottom
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
dp = [-1] * (n + 1)
dp[0] = 1
def DynamicProgramming(num):
if num < 0: return 0
if dp[num] != -1: return dp[num]
else:
root_1 = DynamicProgramming(num-1)
root_2 = DynamicProgramming(num-2)
dp[num] = root_1 + root_2
return dp[num]
return DynamicProgramming(n)
#==============================================================================
class Input:
def __init__(self, num=0):
if num == 1:
self.n = 2
self.ans = 2
elif num == 2:
self.n = 3
self.ans = 3
else:
self.input = 2
### Main ######################################################################
if __name__ == "__main__":
solve()
###############################################################################