Home > libalgo > 分割数

分割数

概要

$n$ 個の互いに区別できない品物を $m$ 個以下のグループに分割する方法の総数のことを分割数といい，動的計画法で求めることができます．

計算量

$O(nm)$

使い方

$n$ 個の互いに区別できない品物を $m$ 個以下のグループに分割する方法の総数を求める．答えは dp[m][n]．

実装

template <int MOD = 1000000007>
std::vector<std::vector<int>> partition_number(int n, int m) {
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
    dp[0][0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (j - i >= 0)
                dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % MOD;
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    return dp;
}

検証

たくさん

参考文系

蟻本