🧗♂️階段を登る問題（Dynamic Programming）
鍛えるためにleetCodeで学習中💪
問題概要
https://leetcode.com/problems/climbing-stairs/description/
1段または2段ずつ登ることができる階段。
n段目にたどり着く方法は何通りあるか？
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
🔍 最初につまずいたこと
- 考え方
DP = Dynamic Programming（動的計画法）とは
「大きな問題を、小さな問題に分けて、部分的な解を使い回しながら最終的な答えを求める」手法
1. dp = [0] * (n+1) の意味
- Pythonのリスト初期化の書き方
→ 長さn+1のリストを、すべて0にする
dp = [0, 0, 0, 0, 0, ...] # 長さn+1
2. dp[i] = dp[i-1] + dp[i-2] の意味
各段 i に来る方法は、以下の2通り：
- i-1 段目から1段登る
- i-2 段目から2段登る
dp[i] = dp[i-1] + dp[i-2]
# これはフィボナッチ数列と同じ構造になる
3. dp[0] = 1 がなぜ1なのか疑問だった
- 実際には「まだ何も登っていない状態」
- でもプログラム的には「登り方のスタートは1通りある」と定義することで、
他の段の計算がうまくできるようになる - これは定義として「そう決めてる」と思ってOK！
✅ 実際のコード
class Solution:
def climbStairs(self, n: int) -> int:
if n == 0 or n == 1:
return 1
dp = [0] * (n+1)
dp[0] = dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
必要なアプローチは？
状態：何を求めたいのか？
→ dp[i] = i段目までの登り方の数
遷移：前の状態からどう移動するのか？
→ dp[i] = dp[i-1] + dp[i-2]