D - Redistribution

[hxrxchang]

https://atcoder.jp/contests/abc178/tasks/abc178_d

概要

整数Sが与えられる。数列の各項が3以上でその総和がSになるような数列の組み合わせはいくつあるか。

解き方

めっちゃDPぽい。 0~Sまでの数列の組み合わせ数は一個前から導けそう。

初期状態を自分自身のみの1項しかない数列とする。 自分より3以上小さい数字は、そこに+3すると自分にできるため、自分より3以上小さい数字の組数の総和が自分の組数になる。 Sは最大2000なので、O(N**2)でも問題ない。

func solve() {
    s := getInt()
    // dp[i]: 数列の総和がiになるような数列の個数
    dp := make([]int, s+1)

    // 初期状態を、自分自身のみの1項しかない数列とする
    for i := 1; i <= s; i++ {
        if i >= 3 {
            dp[i] = 1
        }
    }

    for i := 3; i <= s; i++ {
                // 自分より3以上小さい数字は、そこに+3すると自分にできるため、自分より3以上小さい数字の組数の総和が自分の組数になる。
        for j := 3; j <= i-3; j++ {
            dp[i] += dp[j]
            dp[i] %= MOD
        }
    }

    fmt.Println(dp[s])
}

https://atcoder.jp/contests/abc178/submissions/54411429