POJ 1664 放蘋果 —— 整數分割遞推關係與 DP 解法

POJ 1664 經典題目：將 M 個相同的蘋果放入 N 個相同的盤子，允許空盤，求不同分法數 K。盤子相同意味著 (5,1,1) 與 (1,5,1) 視為同一種分法。資料範圍 M, N ≤ 10，極小，適合遞推 / DP / 記憶化搜索。

一、遞推關係分析

設 f(m, n) 為將 m 個蘋果放入 n 個盤子的方案數。考慮最後一個盤子是否為空，分兩類：

1. 無空盤：每個盤子至少 1 顆 → 先各放 1 顆，剩下 m-n 顆放入 n 個盤子 → f(m-n, n)
2. 有空盤：至少一個盤子為空 → 等價於將 m 顆蘋果放入 n-1 個盤子 → f(m, n-1)

遞推公式：

f(m, n) = f(m-n, n) + f(m, n-1)

二、邊界條件

• m == 0：蘋果已放完，只有一種分法（全空盤）→ 返回 1
• n == 1：只有一個盤子，所有蘋果必須全放進去 → 返回 1
• m < n：蘋果比盤子少，多餘盤子必空 → 等價於 f(m, m)

三、遞歸 + 記憶化實現

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

int dp[11][11]; // M,N ≤ 10

int solve(int m, int n) {
    if (m == 0 || n == 1) return 1;
    if (m < n) return solve(m, m);
    if (dp[m][n]) return dp[m][n];
    return dp[m][n] = solve(m-n, n) + solve(m, n-1);
}

int main() {
    int T; cin >> T;
    while (T--) {
        int M, N; cin >> M >> N;
        memset(dp, 0, sizeof(dp));
        cout << solve(M, N) << endl;
    }
    return 0;
}

四、迭代 DP 版本（自底向上）

int dp[11][11] = {0};
for (int i = 0; i <= 10; ++i) dp[0][i] = dp[i][1] = 1;
for (int m = 1; m <= 10; ++m)
    for (int n = 2; n <= 10; ++n)
        dp[m][n] = (m < n) ? dp[m][m] : dp[m-n][n] + dp[m][n-1];

五、樣例驗證

Input:  7 3
Output: 8
// 分法列舉：(7,0,0) (6,1,0) (5,2,0) (5,1,1) (4,3,0) (4,2,1) (3,3,1) (3,2,2)

六、複雜度與總結

狀態數 O(M·N) = 100，時間 O(1) 查表。本題本質是整數分割數 p(m, n)（將 m 分解為不超過 n 個正整數之和的無序分法數），是組合數學經典模型。