使用一维Integer数组缓存实现二项式系数递归计算遇问题求助

你的代码里的缓存逻辑存在一个关键问题：二项式系数C(n,k)是由两个参数n和k共同决定的，但你只用了一维数组按n来存储值。这意味着同一个n对应的不同k的结果会被互相覆盖，导致缓存返回错误的值。

举个实际例子：当你计算C(4,1)时，代码会把cache[4]设为4；之后如果计算C(4,2)，代码发现cache[4]不为0，就直接返回4，但实际上C(4,2)=6，这就完全错了。

方案1：改用二维数组缓存（最直观的递归修复） #

把缓存改成二维数组cache[n+1][k+1]，用来存储每个(n,k)对对应的二项式系数值，这样就能精准匹配每个计算场景。

修正后的代码：

static public int computeCached(int n, int k) throws IllegalArgumentException {
    if(n < 0 || k < 0 || n < k) 
        throw new IllegalArgumentException("Illegal arguments: n must be >=k >=0");
    // 初始化二维缓存，所有元素默认0
    int[][] cache = new int[n + 1][k + 1];
    return computeCached(n, k, cache);
}

static int computeCached(int n, int k, int[][] cache) throws ArithmeticException {
    if(k == 0 || n == k) 
        return 1;
    // 检查当前(n,k)是否已经缓存
    if(cache[n][k] != 0) 
        return cache[n][k];
    // 递归计算并缓存结果
    cache[n][k] = Math.addExact(computeCached(n-1, k, cache), computeCached(n-1, k-1, cache));
    return cache[n][k];
}

方案2：优化为一维数组缓存（迭代实现，空间更高效） #

如果想继续用一维数组，可以利用二项式系数的递推特性（C(n,k) = C(n-1,k) + C(n-1,k-1)），从底往上迭代计算，一维数组可以复用空间，只需要O(k)的空间复杂度。

示例代码：

static public int computeCachedOneD(int n, int k) throws IllegalArgumentException {
    if(n < 0 || k < 0 || n < k) 
        throw new IllegalArgumentException("Illegal arguments: n must be >=k >=0");
    // 一维缓存，长度为k+1
    int[] cache = new int[k + 1];
    // 初始化C(0,0)=1
    cache[0] = 1;
    // 从n=1迭代到n
    for(int i = 1; i <= n; i++){
        // 从k往1倒序更新，避免覆盖需要的值
        for(int j = Math.min(i, k); j > 0; j--){
            cache[j] = Math.addExact(cache[j], cache[j-1]);
        }
    }
    return cache[k];
}

比如测试computeCached(5,2)应该返回10，computeCached(4,2)返回6，现在两种方案都能正确返回结果，缓存也能正常工作。

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