如何用Python计算n个元素的单/配对组合总数？动态规划求解遇阻

状态定义与基准情况 #

定义dp[n]为n个元素的所有合法组合方式总数。

基准情况：

• dp[0] = 1：0个元素时，只有空组合这一种情况，是递推的基础
• dp[1] = 1：1个元素只能单独存在，仅1种组合方式

递推关系推导 #

考虑第n个元素的两种选择：

1. 单独存在：此时剩下的n-1个元素的组合数为dp[n-1]
2. 与其他元素配对：从前面n-1个元素中选1个和它配对，有n-1种选择；配对完成后，剩下的n-2个元素的组合数为dp[n-2]，这部分贡献为(n-1)*dp[n-2]

因此递推公式为：

dp[n] = dp[n-1] + (n-1)*dp[n-2]

示例验证 #

当n=3时：

• 先计算dp[2] = dp[1] + 1*dp[0] = 1 + 1*1 = 2（对应两种组合：两个元素都单独、两个元素配对）
• 再计算dp[3] = dp[2] + 2*dp[1] = 2 + 2*1 = 4，与示例输出一致

Python实现 #

迭代式动态规划（空间优化版） #

适合处理较大的n，空间复杂度为O(1)：

def count_combinations(n):
    if n == 0 or n == 1:
        return 1
    prev_prev = 1  # 对应dp[0]
    prev = 1       # 对应dp[1]
    for i in range(2, n+1):
        current = prev + (i-1)*prev_prev
        prev_prev, prev = prev, current
    return prev

递归加记忆化 #

可读性更强，通过缓存避免重复计算：

from functools import lru_cache

@lru_cache(maxsize=None)
def count_combinations(n):
    if n == 0 or n == 1:
        return 1
    return count_combinations(n-1) + (n-1)*count_combinations(n-2)

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