java - 硬币兑换 : dynamic programing O(N) complexity

Question

我正在尝试解决以下问题:

给你一组硬币 S。假设你有无限数量的每枚硬币，你可以用多少种方式求和 N。

注意:集合 S 中的硬币将是唯一的。这个问题的预期空间复杂度是 O(N)。请注意，答案可能会溢出。所以，给我们答案 %1000007

我有以下使用 DP 的解决方案

HashMap<Integer, HashMap<Integer, Integer>> memo = new HashMap<>();
public int coinchange2(List<Integer> a, int b) {
    return use(a, 0, b);
}

private int use(List<Integer> a, Integer index, int n) {
    if(memo.containsKey(a.get(index))) {
        if(memo.get(a.get(index)).containsKey(n)) {
            return memo.get(a.get(index)).get(n);
        }
    }
    if(n == 0 && a.get(index)>=0) {
        return 1;
    }
    if((n > 0 && a.get(index) == 0) || n < 0) {
        return 0;
    }
    int nbWays = 0;
    for(int i = index; i < a.size(); i++) {
        nbWays += use(a, i, n - a.get(i))%1000007;
    }

    if(!memo.containsKey(a.get(index))) {
        memo.put(a.get(index), new HashMap<Integer, Integer>());  
    }
    nbWays = nbWays % 1000007;
    memo.get(a.get(index)).put(n, nbWays);
    return nbWays;
}

但是我还是没有达到要求:“部分正确答案。让您的解决方案更高效”

您知道是什么导致此代码不是 O(N) 复杂度吗？

Answer 1

我很确定您可能在复杂度为 O(n) 的 for 循环中递归调用 use()。在第一次运行中，您调用 use() a.size() 次，对 a 中的每个索引调用一次，所以这至少是 O(n^2)，对吧？

您能否逐行调试它，看看您调用了多少次 use()？或者甚至现在每次调用 use() 时只增加一个计数器，这样您就知道您正在运行多少次。

这里的所有其他方法都是 O(1)(我认为)，所以我觉得它必须是那个循环。