求大整数恰好拆分为k个含1的部分的分拆数（Python实现）

问题需求 #

计算将整数恰好拆分为k个部分，且分拆的最小部分为1的分拆数量。例如n=7、k=2时，结果应为3，而非具体的分拆列表[[1,6],[2,5],[3,4]]。现有递归算法仅能生成分拆结果，需用动态规划或记忆化实现计数。

递推思路 #

基于分拆的两种核心情况推导递推公式：

• 分拆包含至少一个1：此时剩余的n-1需拆分为k-1个部分（已用一个1占了一个部分），满足条件的分拆数等于dp[n-1][k-1]
• 分拆所有部分都大于1：给每个部分减1，转化为将n-k拆分为k个部分（每个部分至少为1），满足条件的分拆数等于dp[n-k][k]

最终递推公式：
dp[n][k] = dp[n-1][k-1] + dp[n-k][k]

边界条件 #

• 当k=1时，只有1种分拆（即整数本身），dp[n][1] = 1
• 当n=k时，只有全1的分拆，dp[n][k] = 1
• 当n<k时，无法拆分，dp[n][k] = 0

实现代码 #

动态规划版 #

def count_partitions(n, k):
    # 初始化DP表，dp[i][j]表示将i拆分为j个符合条件的部分的数量
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    
    # 填充边界条件
    for i in range(1, n + 1):
        dp[i][1] = 1
    for i in range(1, min(n, k) + 1):
        dp[i][i] = 1
    
    # 填充DP表
    for i in range(2, n + 1):
        for j in range(2, min(i, k) + 1):
            dp[i][j] = dp[i-1][j-1] + dp[i-j][j]
    
    return dp[n][k]

# 测试示例
print(count_partitions(7, 2))  # 输出3

记忆化递归版 #

from functools import lru_cache

@lru_cache(maxsize=None)
def count_partitions_recursive(n, k):
    if k == 1:
        return 1
    if n == k:
        return 1
    if n < k:
        return 0
    return count_partitions_recursive(n-1, k-1) + count_partitions_recursive(n-k, k)

# 测试示例
print(count_partitions_recursive(7, 2))  # 输出3

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