每日算法 — 使用java实现整数划分：动态规划与划分数递推计算

问题引入

整数划分是数论与组合数学中的经典问题：给定一个正整数 n，求将其表示为若干个正整数之和的方案数。例如 n=4 时，共有 5 种划分：(4)、(3+1)、(2+2)、(2+1+1)、(1+1+1+1)。注意划分不考虑顺序，3+1 与 1+3 视为同一种。本文用Java实现多种动态规划解法，并延伸到限制最大部分、限制部分个数等变体。

算法原理

核心状态定义

设 dp[n][k] 表示将整数 n 划分为最大部分不超过 k 的方案数。状态转移分两种情况：

1. 划分中包含至少一个 k：去掉一个 k 后，问题变为 dp[n-k][k]
2. 划分中不包含 k：最大部分不超过 k-1，即 dp[n][k-1]

转移方程：

dp[n][k] = dp[n-k][k] + dp[n][k-1]

边界条件：dp[0][k] = 1（空划分算一种），dp[n][1] = 1（只能全用1）。

一维空间优化

观察到 dp[n][k] 只依赖当前行和上一行，可压缩为一维数组：

for k from 1 to n:
    for i from k to n:
        dp[i] += dp[i-k]

这等价于完全背包问题——将容量为 n 的背包用面值为 1 到 n 的物品恰好装满的方案数。

五边形数定理（进阶）

欧拉发现的五边形数定理给出了划分数的递推公式：

p(n) = Σ (-1)^(k+1) × [p(n - k(3k-1)/2) + p(n - k(3k+1)/2)]

该定理将划分数的计算复杂度降至 O(n√n)，是计算大整数划分的利器。

Java完整实现

import java.util.Arrays;

/**
 * 整数划分算法实现
 * 包含基础DP、空间优化、限制条件变体及五边形数定理
 */
public class IntegerPartition {

    /**
     * 方法一：二维动态规划
     * dp[i][j] = 将i划分为最大部分不超过j的方案数
     * 时间复杂度 O(n^2)，空间复杂度 O(n^2)
     */
    public int partitionCount2D(int n) {
        int[][] dp = new int[n + 1][n + 1];

        // 初始化：dp[0][j] = 1，空划分算一种
        for (int j = 0; j <= n; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (j > i) {
                    dp[i][j] = dp[i][i]; // 最大部分不能超过i本身
                } else {
                    // 包含至少一个j + 不包含j
                    dp[i][j] = dp[i - j][j] + dp[i][j - 1];
                }
            }
        }

        return dp[n][n];
    }

    /**
     * 方法二：一维动态规划（完全背包优化）
     * 时间复杂度 O(n^2)，空间复杂度 O(n)
     */
    public int partitionCount1D(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1; // 空划分

        // 外层循环遍历可用数字（物品）
        for (int k = 1; k <= n; k++) {
            // 内层循环遍历容量，正序（完全背包）
            for (int i = k; i <= n; i++) {
                dp[i] += dp[i - k];
            }
        }

        return dp[n];
    }

    /**
     * 方法三：限制最大部分为maxPart的划分数
     * 时间复杂度 O(n × maxPart)，空间复杂度 O(n)
     */
    public int partitionWithMaxPart(int n, int maxPart) {
        int[] dp = new int[n + 1];
        dp[0] = 1;

        for (int k = 1; k <= maxPart; k++) {
            for (int i = k; i <= n; i++) {
                dp[i] += dp[i - k];
            }
        }

        return dp[n];
    }

    /**
     * 方法四：限制恰好划分为k个部分的方案数
     * dp[i][j] = 将i恰好划分为j个部分的方案数
     * 转移：至少一个1 → dp[i-1][j-1]；所有部分都>1 → 每个部分减1 → dp[i-j][j]
     */
    public int partitionIntoKParts(int n, int k) {
        int[][] dp = new int[n + 1][k + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k && j <= i; j++) {
                // 至少一个1 + 所有部分>=2（每个减1后等价于将i-j划分为j部分）
                dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];
            }
        }

        return dp[n][k];
    }

    /**
     * 方法五：五边形数定理（欧拉递推）
     * 时间复杂度 O(n√n)，空间复杂度 O(n)
     * 适合计算大整数划分数，结果可能很大需用BigInteger
     */
    public long partitionPentagonal(int n) {
        long[] p = new long[n + 1];
        p[0] = 1;

        for (int i = 1; i <= n; i++) {
            long sum = 0;
            int k = 1;
            // 五边形数 gk = k(3k-1)/2
            while (true) {
                int g1 = k * (3 * k - 1) / 2;
                int g2 = k * (3 * k + 1) / 2;

                if (g1 > i && g2 > i) break;

                long sign = (k % 2 == 1) ? 1 : -1;
                if (g1 <= i) sum += sign * p[i - g1];
                if (g2 <= i) sum += sign * p[i - g2];

                k++;
            }
            p[i] = sum;
        }

        return p[n];
    }

    /**
     * 打印划分数表格（调试用）
     */
    public void printPartitionTable(int n) {
        int[][] dp = new int[n + 1][n + 1];
        for (int j = 0; j <= n; j++) dp[0][j] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (j > i) dp[i][j] = dp[i][i];
                else dp[i][j] = dp[i - j][j] + dp[i][j - 1];
            }
        }

        System.out.println("划分数表格 p(n, max=k):");
        for (int i = 0; i <= n; i++) {
            System.out.println("n=" + i + ": " + Arrays.toString(dp[i]));
        }
    }

    public static void main(String[] args) {
        IntegerPartition solver = new IntegerPartition();
        int n = 10;

        System.out.println("=== 整数划分算法演示 (n=" + n + ") ===\n");

        System.out.println("二维DP结果: " + solver.partitionCount2D(n));
        System.out.println("一维优化结果: " + solver.partitionCount1D(n));
        System.out.println("五边形数定理结果: " + solver.partitionPentagonal(n));

        System.out.println("\n限制最大部分为5: " + solver.partitionWithMaxPart(n, 5));
        System.out.println("恰好划分为3部分: " + solver.partitionIntoKParts(n, 3));

        System.out.println("\n划分数表格 (n=0~6):");
        solver.printPartitionTable(6);

        // 验证五边形数定理
        System.out.println("\n五边形数定理验证:");
        for (int i = 0; i <= 10; i++) {
            System.out.println("p(" + i + ") = " + solver.partitionPentagonal(i));
        }
    }
}

复杂度分析

扩展思考

1. 生成函数视角：整数划分的普通生成函数为 P(x) = Π(1/(1-x^k))，五边形数定理正是该无穷乘积的倒数展开结果。
2. 不同部分划分：若要求划分中的各部分互不相同，状态转移变为 dp[i][j] = dp[i-j][j-1] + dp[i][j-1]（要么包含一个j且其余部分不超过j-1，要么不包含j）。
3. 奇偶部分划分：限制所有部分均为奇数，或限制所有部分互不相同——这两者之间存在一一对应关系（欧拉定理），可通过Ferrers图的对称性证明。

整数划分是组合数学的基石问题之一，其动态规划解法与完全背包问题的等价性，深刻揭示了”计数”与”优化”两类问题在算法结构上的内在统一。