漸化式アルゴリズムサンプル(golang)

何が書いてあるか

漸化式のアルゴリズムのGo版。備忘録用。

適用ケース

N段の階段をA段飛ばし、B段飛ばしで登ったときの、各段ごとにとれる登るパターン数を計算する。　など
上記ケースでのコード例）

package main
import "fmt"
func main(){
    dp:=make([]int,N+1)
    dp[0]=1

    for i:=1;i<=N;i++ {
        dp[i]=0
        if i>=A {
            dp[i]=dp[i]+dp[i-A]
        }
        if i>=B {
            dp[i]=dp[i]+dp[i-B]
        }
    }
    // ここから続く5行は、頂上手前で飛ばす段数よりも残り段数が少ない場合には、頂上に到達させるとする場合のルート数の計算。
    end:=0
    for i:=N-1;i>=N-A+1;i-- {
        end+=dp[i]
    }
    dp[N]+=end

    // 段ごとの階段の選び方の総数の全段分を表示。
    fmt.Println(dp)
}