70. Climbing Stairs

あなたは階段を上っています。頂上にたどり着くには n 段のステップが必要です。

一度に 1 段または 2 段のステップを登ることができます。
頂上まで登るには何通りの異なる方法がありますか？

---

例 1：

入力: n = 2
出力: 2
説明: 頂上まで登る方法は 2 通りあります。

1. 1 段 + 1 段
2. 2 段

---

例 2：

入力: n = 3
出力: 3
説明: 頂上まで登る方法は 3 通りあります。

1. 1 段 + 1 段 + 1 段
2. 1 段 + 2 段
3. 2 段 + 1 段

---

1. n = 1 または n = 2 の場合、n をそのまま返す
   → それぞれ方法は 1通り、2通りしかないので特別扱い

2. dp 配列を n+1 要素で初期化
   → インデックスを 1 から n まで使いたいので、サイズは n+1 に

3. dp[1] = 1、dp[2] = 2 にセット
   → 基本ケース（初期値）を設定

4. for 文で i を 3 から n までループ
   → 各ステップに到達する方法は「1つ前から来る＋2つ前から来る」の合計

5. 最終的に dp[n] を返す