为什么这是我的简单缓存不工作

Question

我写了一段代码

private int CountChangeOptions(int[] coins, int j, int N)
{   
    if(j == 0)
        return 0;
    if(N == 0)
        return 1;
    if(j == 1)
        return N % coins[0] == 0 ? 1 : 0;
    int sum = 0;
    int k = coins[j - 1];
    for(int i = N; i >= 0; i -= k)
    {
        sum += CountChangeOptions(coins, j - 1, i);
    }
    return sum;
}

计算正确(尽管不够快)。由于CountChangeOptions(coins, x, y)对于大多数coins将在算法过程中被多次调用相同的x, y我决定实现一个缓存策略

private int CountChangeOptions(int[] coins, int j, int N)
{   
    if(j == 0)
        return 0;
    if(N == 0)
        return 1;
    if(j == 1)
        return N % coins[0] == 0 ? 1 : 0;
    int sum = 0;
    int k = coins[j - 1];
    for(int i = N; i >= 0; i -= k)
    {
        sum += CountOrGetFromCache(coins, j - 1, i);
    }
    return sum;
}
private int CountOrGetFromCache(int[] coins, int j, int i)
{
    if(_cache[j, i] == null)
    {
       _cache[j, i] = CountChangeOptions(coins, j, i);
    }
    return (int)_cache[j, i];
}

，其中_cache是int?[][]，之前已经用_cache = new int[N+1, N+1]设置了。然而，这在一些测试用例中失败了。知道为什么吗?

Answer 1

我看到的唯一问题是_cache变量被错误地初始化为

_cache = new int[N+1, N+1]

代替

_cache = new int[coins.Length+1, N+1]

除此之外，两种解决方案在功能上是相同的。我不相信有一个功能测试用例在第一个(缓慢的)实现中工作，而在第二个实现中失败。

我猜你正在使用一些网站，如HackerRank或其类似的，和第一个解决方案可能超时，给你的感觉，它的工作和第二个更快不会超时，但产生不正确的结果。