遞歸法解決整數劃分問題：原理與實現

問題定義

將正整數 n 表示為一系列遞減正整數之和：n = n₁ + n₂ + ... + nₖ，其中 n₁ ≥ n₂ ≥ ... ≥ nₖ ≥ 1, k ≥ 1。不同劃分個數記為 p(n)。例：p(6) = 11。

遞歸模型構建：引入輔助函數 q(n, m)

定義 q(n, m) 為：正整數 n 的所有劃分中，最大加數不超過 m 的劃分個數。目標 p(n) = q(n, n)。

遞歸關係推導

1. 邊界 1：q(n, 1) = 1 (n ≥ 1)
   最大加數 ≤ 1 ⇒ 唯一劃分：n = 1 + 1 + ... + 1 (n 個 1)。
2. 邊界 2：q(n, m) = q(n, n) (m ≥ n)
   最大加數不能超過 n，故 m 超過 n 時等價於 m = n。
3. 遞歸 1：q(n, n) = q(n, n-1) + 1
   劃分分為兩類：① 最大加數 = n (僅 1 種：n 本身)；② 最大加數 ≤ n-1 (即 q(n, n-1))。
4. 遞歸 2 (核心)：q(n, m) = q(n, m-1) + q(n-m, m) (n > m > 1)
   劃分分為兩類：① 最大加數 = m ⇒ 剩餘 n-m 最大加數仍 ≤ m，即 q(n-m, m)；② 最大加數 ≤ m-1，即 q(n, m-1)。

代碼實現 (C++)

#include <iostream>
#include <vector>
using namespace std;

// 遞歸 + 備忘錄 (動態規劃優化)
vector<vector<long long>> memo;

long long q(int n, int m) {
    if (n < 1 || m < 1) return 0;
    if (m == 1) return 1;                 // 邊界 1
    if (m >= n) return q(n, n);           // 邊界 2
    if (memo[n][m] != -1) return memo[n][m];
    
    if (m == n) {
        memo[n][m] = q(n, n-1) + 1;       // 遞歸 1
    } else { // n > m > 1
        memo[n][m] = q(n, m-1) + q(n-m, m); // 遞歸 2
    }
    return memo[n][m];
}

long long partition(int n) {
    memo.assign(n+1, vector<long long>(n+1, -1));
    return q(n, n);
}

int main() {
    for (int i = 1; i <= 20; ++i) {
        cout << "p(" << i << ") = " << partition(i) << endl;
    }
    // p(6) = 11 驗證
    return 0;
}

關鍵理解點

• 狀態定義精準：q(n, m) 以「最大加數上限」為狀態參數，將問題分解為「包含 m」與「不包含 m」兩個互斥子問題
• 遞歸 2 是核心：q(n, m) = q(n, m-1) + q(n-m, m) 對應「最大加數 = m」與「最大加數 < m」的完全分割
• 備忘錄優化：避免重複計算，時間複雜度從指數級降至 O(n²)

擴展思考

若需輸出所有具體劃分方案，可在遞歸中維護路徑向量；若需生成第 k 個劃分（字典序），可利用 q(n, m) 的計數特性進行「跳躍式」構造，避免全量枚舉。