分割数

[参考元]
・秋葉拓哉,岩田陽一,北川宜稔「プログラミングコンテストチャレンジブック第2版」株式会社マイナビ、2010,pp.66-67
・分割数-Wikipedia
・動的計画法

蟻本の「分割数」が理解するのが難しかったのでメモ。

蟻本の「分割数」の問題文は
n個の互いに区別できない品物を、m個以下に分割する方法の総数を求め、Mで割った余りを答えなさい。
蟻本より

この問題文を別の言い方で表すと、「自然数nをその順番の違いを除いてm以下の和で表す方法の総数を求め、Mで割った余りを答えなさい。」となる。これを、p(n, m)と表す。

例）
n = 4, m = 3の場合を考える。品物を○、分割を|で表す。
○と｜の列が蟻本の問題文の解釈、下の列が別の言い方で表した場合。

○　｜　○　｜　○○
１　＋　１　＋　２

となる。
ただし、次の分け方は下の分け方と同じである。

○　｜　○○　｜　○
１　＋　２　　＋　１

[１]　p(n, m)を深さ優先探索で求める。

p(n', m')はp(n', m' - 1)とp(n' - m', m')の和として表せる。
・p(n', m' - 1)はn'をm'-1以下の和で表した場合の総数。すなわち、n'を表すのにm'を使わなかった場合。
・p(n' - m', m')はnを表すのに一つのm'を使った場合の総数。すなわち、n'を表すのにm'を使った場合。

ただし、p(0, m')=1、p(n',1)=1である。
また、mの値が減少していくように探索しているので、1+1+2や1+2+1などを2+1+1と一通りで数える。

#include <iostream>

using namespace std;

const int MAX_N = 1000;
const int MAX_M = 1000;

int n, m, M;

// 深さ優先探索
int p(int n, int m)
{
    int ret;

    if(n == 0 || m == 1)
        return 1;

    ret = p(n, m - 1);
    if(n >= m)
        ret += p(n - m, m);

    return ret;
}

void solve()
{
    cout << p(n, m) % M << endl;
    
}

int main()
{
    cin >> n >> m >> M;
    solve();

    return 0;
}

[２]メモ化をする

大きなnに対しては、p(n, m)が何度か呼ばれていることが分かる。
なので、引数の組(n, m)に対してメモ化を行う。
main関数は省略

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 1000;
const int MAX_M = 1000;

int n, m, M;
int memo[MAX_N + 1][MAX_M + 1]; // メモ化

int p(int n, int m)
{
    int ret;

    if (memo[n][m] >= 0)
        return memo[n][m];

    if(n == 0 || m == 1)
        return 1;

    ret = p(n, m - 1);
    if(n >= m)
        ret += p(n - m, m);

    return memo[n][m] = ret;
}

void solve()
{
    memset(memo, -1, sizeof(memo));
    cout << p(n, m) % M << endl;
}

[３]動的計画法

[２]のメモ化を動的計画法に持ち込む。
※蟻本ではdp[i][j] := jのi分割の総数としているが、
上の[２]に合わせるためにdp[i][j] := iのj分割の総数とした。
初期化の部分は[２]と対応をとりやすいように冗長に書いた。

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 1000;
const int MAX_M = 1000;

int n, m, M;
int dp[MAX_N + 1][MAX_M + 1]; // dp

void solve()
{
    for (int i = 0; i <= m; i++)
        dp[0][i] = 1;
    for (int i = 0; i <= n; i++)
        dp[i][1] = 1;

    for (int i = 0; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (i >= j) 
                dp[i][j] = (dp[i][j - 1] + dp[i - j][j]) % M;
            else
                dp[i][j] = dp[i][j - 1];
        }
    
    cout << dp[n][m] << endl;
}