COINCHANGE:O(N)复杂性的动态编程

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（），对中的每个索引都调用一次，所以这至少是O（n^2），对吧？

你能一行一行地调试它，看看你调用了use（）多少次吗？或者现在只需在每次调用use（）时增加一个计数器，这样您就可以知道要运行多少次了。

你在这里的所有其他方法都是O（1）（我想），所以我觉得它一定是那个循环。

Answer 2

变更问题可以在维基百科上找到。这里的代码是用Python编写的。GeeksforGeeks有C/C++的解决方案，在语法上更接近Java。请花点时间完全阅读其中一个或另一个，以理解解决方案。