如何快速计算给定数值的非递减整数分拆组合数

你要解决的问题本质是整数分拆问题——统计将N拆分为任意个正整数之和，且拆分后的数非递减（等价于不计顺序的分拆）的组合总数。原递归代码因暴力枚举+大量重复计算，在N=200时速度极慢，下面提供两种高效解决方案：

一、动态规划（最优方案） #

思路 #

用一维数组dp缓存中间结果：

• dp[i]表示和为i的非递减组合数量
• 初始条件dp[0] = 1（和为0的组合只有空组合1种）
• 遍历每个可能的数j（从1到N），再遍历i从j到N，更新dp[i] += dp[i-j]——逻辑是：给所有和为i-j的组合末尾加上j，保证组合非递减（因为j从小到大遍历，之前的组合元素都≤j）

代码实现（JavaScript） #

function countIntegerPartitions(N) {
    const dp = new Array(N + 1).fill(0);
    dp[0] = 1; // 基准情况：和为0的组合有1种
    
    for (let j = 1; j <= N; j++) {
        // 从j开始遍历，确保加入的数不小于当前j，维持非递减
        for (let i = j; i <= N; i++) {
            dp[i] += dp[i - j];
        }
    }
    
    return dp[N];
}

// 测试示例
console.log(countIntegerPartitions(1)); // 1
console.log(countIntegerPartitions(2)); // 2
console.log(countIntegerPartitions(3)); // 3
console.log(countIntegerPartitions(4)); // 5
console.log(countIntegerPartitions(5)); // 7
console.log(countIntegerPartitions(200)); // 瞬间出结果

这个方案时间复杂度为O(N²)，空间复杂度为O(N)，对于N=200来说完全无压力，比原递归快几个数量级。

二、记忆化递归（优化版递归） #

如果更倾向递归写法，可以给原递归加上缓存，避免重复计算相同子问题：

代码实现（JavaScript） #

function countIntegerPartitionsMemo(N) {
    const memo = new Map();
    
    function helper(remaining, start) {
        if (remaining === 0) return 1;
        if (start > remaining) return 0;
        
        const key = `${remaining},${start}`;
        if (memo.has(key)) return memo.get(key);
        
        // 选start：剩余值减去start，继续从start开始选（保证非递减）
        // 不选start：从start+1开始选
        const count = helper(remaining - start, start) + helper(remaining, start + 1);
        memo.set(key, count);
        return count;
    }
    
    return helper(N, 1);
}

// 测试
console.log(countIntegerPartitionsMemo(200)); // 比原递归快很多

这个方案通过缓存(remaining, start)的计算结果，避免了原递归中大量重复的函数调用，速度提升明显，但相比动态规划仍有函数调用的开销。

内容的提问来源于stack exchange，提问作者valerii15298