LeetCodeの階段の問題:原因分析と解決方法

以下に、階段の問題を解くためのシンプルで簡単な方法とコード例を示します。

1. 再帰的なアプローチ: 再帰的なアプローチを使用して階段の問題を解く場合、以下のような再帰関数を定義します。

def climbStairs(n):
    if n <= 2:
        return n
    return climbStairs(n-1) + climbStairs(n-2)

この関数は、nが1以下の場合にはnを返し、それ以外の場合には前の2つの階段の組み合わせ数の和を返します。

2. 動的計画法: 動的計画法を使用して階段の問題を解く場合、メモ化テーブルを使用して計算結果を保存します。以下に、動的計画法を用いた解法のコード例を示します。

def climbStairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

このコードでは、dpというリストを作成し、n段までの階段を登る方法の数を保存します。ループを使って、dp[i] = dp[i-1] + dp[i-2] の関係を使って計算していきます。

以上が、LeetCodeの階段の問題を解くためのシンプルで簡単な方法とコード例です。再帰的なアプローチと動的計画法の両方を使用していますが、動的計画法の方が効率的です。