paizaの練習問題を解く階段の上り方 1 Go編

こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

階段の上り方 1 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】

実装

ヒントにあるような実装をそのままgoに書き起こしました。

package main
import "fmt"
func main(){
    var n int
    fmt.Scan(&n)
    dp := make([]int, n + 1)
    dp[0] = 1
    for i := 1; i <= n; i++ {
        if i >= 1 {
            dp[i] += dp[i - 1]
        }
        if i >= 2 {
            dp[i] += dp[i - 2]
        }
    }
    fmt.Println(dp[n])
}

この実装、なんとフィボナッチ数列と同じ結果になるんですね。不思議～。

考え方としては、0段は一通り（上らない）として、それ以降の場合の上り方がどのように増えていくかというのを考えるのですが、まず1段ずつ上る場合というのが必ず一通りあるのでdp[i] += dp[i - 1]が成り立ちます。

つまり条件i >= 1の場合、dp[i]は毎回必ず1通りになります。

これに2段で上れる方法が追加されたとき、まず2段のときは2段で上る方法と1段ずつ上る方法の二通りになります。

3段上るときは1段ずつ、2段と1段、1段と2段の三通りになります。

4段になると1段ずつ、1段2段1段、2段1段1段、1段1段2段、2段ずつの5通り…となります。

…確かに並べるとフィボナッチ数列です。

ではなぜそうなるか。

…ちょっと僕では説明できなさそうなので、AIに聞きました。

たとえば、あなたが今「10段目」にたどり着いたとします。その「1歩前」を思い出してみてください。

1歩で1段か2段しかのぼれないなら、10段目に来る直前は、絶対にこの2つのどちらかにいたはずです。

9段目にいて、あと「1段」のぼった
8段目にいて、あと「2段」いっぺんにのぼった

これ以外の場所から10段目にワープすることはできませんよね。

確かにそうですね。。

nで考えて難しいなら、n - 1で考えるというアプローチは大切ですね。

ということで今回はこれで👍

実装#

実装