階段の上り方 1 PHP編（paizaランク B 相当）

整数 n が与えられます。
階段を上るのに、1 歩で 1 段または 2 段を上ることができるとき、n 段の階段を上る方法は何通りあるでしょうか。

---

(ヒント)

これまでは問題文中に具体的な漸化式が書かれていましたが、この問題にはありません。自分で漸化式を立てる必要があります。

部分問題として、1 ~ n-1 段の階段を上る方法が何通りあるか、という問題を考えてみましょう。この部分問題の答えが求まっているとして、n 段の階段を上る方法が何通りあるかを考えてみましょう。n 段目に到達するには、n-1 段目から1段上る方法と、n-2 段目から2段上る方法の2種類が考えられます。dp[n] を n 段の階段を上る方法の数とすれば、この関係は dp[n] = dp[n-1] + dp[n-2] で表すことが出来ます。よって、0段の階段を上る方法が1通り (何もしない) であることを踏まえると、以下のようにして答えを求めることが出来ます。

dp[0] <- 1

for i = 1 to n
    dp[i] <- 0
    if i >= 1 then
        dp[i] <- dp[i] + dp[i-1]    // i-1 段目から1段上って i 段へ到達
    if i >= 2 then
        dp[i] <- dp[i] + dp[i-2]    // i-2 段目から2段上って i 段へ到達

print dp[n]

このような場合分けをすると上で考察した漸化式を満たす配列が実現できます (ピンとこなければ、i に具体的な値を入れて dp[i] がどのように計算されるのか、その処理を追ってみましょう) 。この場合分けは今のところ冗長に見えますが、次の問題を解くときに活きてきます。