如何为计算C(n,k)的递归函数添加Memoization以提升性能？

原递归函数的问题在于会重复计算大量相同的子问题，比如计算C(5,2)时，C(3,1)会被多次调用计算，n越大重复计算的次数呈指数级增长，导致性能急剧下降。记忆化的核心思路是把已经计算过的子问题结果缓存起来，后续再遇到相同子问题时直接返回缓存值，避免重复计算。

优化前置技巧：利用组合数对称性 #

组合数满足 C(n,k) = C(n, n-k)，所以可以先把k替换为Math.min(k, n-k)，这样能减少一半的子问题数量，既节省缓存空间，也减少计算量。

具体实现方式 #

方式1：静态二维数组缓存（适合已知n最大范围的场景）

用二维数组存储已计算的C(n,k)结果，数组大小可根据实际业务中n的最大值调整：

private static Long[][] memo;

public static long choose(int n, int k) {
    // 利用对称性缩小计算范围
    k = Math.min(k, n - k);
    
    // 第一次调用时初始化缓存数组
    if (memo == null) {
        // 假设业务中n的最大值为1000，可按需修改
        int maxN = 1000;
        memo = new Long[maxN + 1][maxN / 2 + 1];
    }

    // 边界条件
    if (k == 0 || k == n) {
        return 1L;
    }

    // 缓存命中则直接返回
    if (memo[n][k] != null) {
        return memo[n][k];
    }

    // 计算子问题并缓存结果
    long result = choose(n-1, k) + choose(n-1, k-1);
    memo[n][k] = result;
    return result;
}

方式2：HashMap缓存（适合n范围不确定的场景）

用键值对存储已计算的结果，键可以用n,k拼接的字符串：

private static Map<String, Long> memo = new HashMap<>();

public static long choose(int n, int k) {
    k = Math.min(k, n - k);
    String key = n + "," + k;

    if (k == 0 || k == n) {
        return 1L;
    }

    // 检查缓存是否存在
    if (memo.containsKey(key)) {
        return memo.get(key);
    }

    long result = choose(n-1, k) + choose(n-1, k-1);
    memo.put(key, result);
    return result;
}

方式3：局部缓存（避免静态变量，适合多线程/多次独立调用场景）

把缓存作为参数传递给内部递归方法，每次调用choose时创建对应大小的缓存，避免静态变量的线程安全问题：

public static long choose(int n, int k) {
    k = Math.min(k, n - k);
    // 每次调用创建对应大小的局部缓存
    Long[][] memo = new Long[n + 1][k + 1];
    return chooseMemoized(n, k, memo);
}

private static long chooseMemoized(int n, int k, Long[][] memo) {
    if (k == 0 || k == n) {
        return 1L;
    }

    if (memo[n][k] != null) {
        return memo[n][k];
    }

    long result = chooseMemoized(n-1, k, memo) + chooseMemoized(n-1, k-1, memo);
    memo[n][k] = result;
    return result;
}

优化效果说明 #

加入记忆化后，每个子问题C(i,j)只会被计算一次，时间复杂度从原来的O(2^n) 降低到O(n²)，空间复杂度为O(n²)（根据缓存结构略有差异），处理较大n值时性能会有显著提升。

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