COINCHANGE：动态编程O（N）复杂

您将得到一套硬币S的在你有多少种方法可以使之ň假设你有各自的无限量在集合中的硬币。

注意：集合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）的复杂性吗？

来源

2016-08-02 Jerome Ansia

我敢肯定，它可能是你递归调用使用（）在for循环有O（n）。在第一次运行中，你调用use（）a.size（）次，一次对于a中的每个索引，所以这至少是O（n^2），对吧？

你可以一行一行地调试它，也许看到你有多少次调用use（）？或者甚至现在只需每次调用use（）时增加一个计数器，这样您就可以知道您正在经历多少次运行。

这里的所有其他方法都是O（1）（我认为），所以我觉得它就是那个循环。

来源

2016-08-02 20:32:26

我想你是对的使用指示O（n^2）的复杂性，谢谢！ –

你把我放在了好的轨道上，我会重写这个版本，并添加一个带有O（N）复杂度的Java版本的响应。 –

听起来不错！我很高兴看到你如何解决它！ –

可以在Wikipedia上找到更改问题。这里的代码是用Python编写的。 Geeks for Geeks在C/C++中有解决方案，这在句法上更接近于Java。请花时间阅读其中一个或另一个，以了解解决方案。

来源

2016-08-02 20:48:31

欢迎来到Stack Overflow！一个潜在的解决方案的链接总是受欢迎的，但请[在链接周围添加上下文]（// meta.stackoverflow.com/a/8259/169503），以便您的同行用户可以了解它是什么以及它为什么在那里。如果目标网站无法访问或永久离线，请始终引用重要链接中最相关的部分。考虑到_仅仅是一个外部网站的链接_可以[导致你的答案被删除]（// stackoverflow.com/help/deleted-answers）。 –

COINCHANGE：动态编程O（N）复杂

回答

相关问题