POJ 3014 Cake Pieces and Plates：整數拆分動態規劃

題目大意

將整數 m 拆分為 n 個非負整數之和（允許 0），求拆分方案數模 1e9+7。n, m ≤ 4500。

動態規劃建模

狀態定義

h(m, n)：將 m 拆成 n 個數（允許 0）的方案數。等價於將 m 拆成 ≤n 個正整數的方案數（在 n 個位置中插入 0）。

遞推關係

• 若 i==1 || j==1：a[i][j] = 1（只有一種拆法）
• 若 j > i：a[i][j] = a[i][i]（多出的位置只能填 0）
• 若 j == i：a[i][j] = a[i][j-1] + 1（多出一種全 1 的拆法）
• 否則：a[i][j] = (a[i][j-1] + a[i-j][j]) % mod
  　　不選 j：a[i][j-1]；選至少一個 j：a[i-j][j]（扣除一個 j 後繼續拆）。

完整代碼

#include <iostream>
using namespace std;
const int maxN = 4500;
const int mod = 1000000007;
int a[maxN+10][maxN+10];
int main() {
    int m, n;
    scanf("%d%d", &n, &m); // 注意輸入順序：n m
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) {
            if (i == 1 || j == 1) a[i][j] = 1;
            else if (j > i) a[i][j] = a[i][i];
            else if (j == i) a[i][j] = (a[i][j-1] + 1) % mod;
            else {
                a[i][j] = a[i][j-1] + a[i-j][j];
                if (a[i][j] >= mod) a[i][j] -= mod;
            }
        }
    printf("%d\n", a[m][n] % mod);
    return 0;
}

關鍵點

• 輸入順序為 n m，題目描述易誤讀，需注意。
• 滾動數組可優化空間至 O(m)，但 4500² ≈ 20M int 約 80MB，通常允許。
• 模運算用減法避免溢出：if (x >= mod) x -= mod;。

數學聯繫

此題 h(m,n) 即分拆數 p(m,n)（將 m 分拆為 ≤n 個正整數），與生成函數、五邊形數定理有深層聯繫。