算法精講：整數劃分數（Partition Number）動態規劃求解與模運算 C 實現

算法精講：整數劃分數（Partition Number）動態規劃求解與模運算 C 實現

整數劃分問題問：「將 n 寫成若干正整數之和（順序不計）有多少種方法？」本文從組合數學定義、動態規劃遞推構造、二維/一維空間實現、模運算處理、生成函數理論視角五個維度，提供完整解題框架。

問題形式化定義

• 輸入：正整數 n、最大劃分數 m、模數 M
• 輸出：n 的不超過 m 個部分的劃分數 mod M
• 示例：n=4, m=3 → 劃分：4、3+1、2+2、2+1+1 → 共 4 種

數學定義與遞推關係

設 p(n, m) = 將 n 劃分為不超過 m 個正整數的方法數。

核心遞推公式

p(n, m) = p(n, m-1) + p(n-m, m)   (n ≥ m > 0)

// 邊界條件
p(0, m) = 1          // 空劃分算 1 種
p(n, 0) = 0 (n>0)    // 正整數不可劃分為 0 個部分
p(n, m) = 0 (n<0)    // 負數無劃分

組合意義解析

• p(n, m-1)：不使用 數字 m 的劃分（所有部分 ≤ m-1）
• p(n-m, m)：至少使用一個 m，剩餘 n-m 繼續劃分（部分仍 ≤ m）
• 二者互斥且窮盡 → 相加

二維 DP 實現（標準教學版）

#include <stdio.h>
#include <string.h>

#define MAX_N 1000
#define MAX_M 1000

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

int partition_2d() {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;  // 關鍵初始化
    
    for (int i = 1; i <= m; i++) {       // 部分數上限
        for (int j = 0; j <= n; j++) {   // 目標和
            dp[i][j] = dp[i-1][j];       // 不用 i
            if (j >= i) {
                dp[i][j] = (dp[i][j] + dp[i][j-i]) % M;  // 至少用一個 i
            }
        }
    }
    return dp[m][n];
}

int main() {
    n = 4; m = 3; M = 10000;
    printf("result = %d\n", partition_2d());  // 4
    return 0;
}

一維空間優化 O(n) 空間

int partition_1d() {
    static int dp[MAX_N + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    
    for (int i = 1; i <= m; i++) {
        // 正序遍歷 j (i 到 n) —— 完全背包模式！
        for (int j = i; j <= n; j++) {
            dp[j] = (dp[j] + dp[j-i]) % M;
        }
    }
    return dp[n];
}

關鍵洞察： 整數劃分 本質上是完全背包問題：物品為 1..m，每種重量=價值=面值，無限件，恰裝滿容量 n 的方案數。

測試用例驗證

# n=4, m=3
劃分: 4 | 3+1 | 2+2 | 2+1+1
結果: 4

# n=5, m=5 (無限制劃分數 p(5))
劃分: 5 | 4+1 | 3+2 | 3+1+1 | 2+2+1 | 2+1+1+1 | 1+1+1+1+1
結果: 7

# n=10, m=10
p(10) = 42

# n=100, m=100, M=1e9+7
需用長整型/大數，結果: 792070839 (mod 1e9+7)

生成函數理論視角（數學深度）

劃分數生成函數：

P(x) = ∏_{k=1}^{∞} 1/(1 - x^k)
     = 1 + x + 2x² + 3x³ + 5x⁴ + 7x⁵ + 11x⁶ + ...
// 係數即 p(n)

• 歐拉五角數定理給出遞推：p(n) = Σ (-1)^{k-1} p(n - k(3k-1)/2)
• 哈迪-拉馬努金漸近公式：p(n) ~ 1/(4n√3) exp(π√(2n/3))

變體擴展

工程實現細節

1. 模運算：(a + b) % M 防溢出，M 可為質數或任意整數
2. 大數支持：M=0 時輸出完整值，需大整數庫（GMP/手寫高精度）
3. 初始化：dp[0]=1 是「空劃分」語義，不可漏
4. 循環順序：外層部分值/種類，內層目標和正序 → 完全背包

複雜度總結

整數劃分問題將組合計數、動態規劃、生成函數、數論漸近分析串聯成一條完美知識鏈。掌握「完全背包視角」與「一維正序遍歷」模式，不僅能秒殺劃分數，更能觸類旁通硬幣找零、郵票面值設計、資源分配方案計數等同構問題。