6

{1,3,5}面额硬币；Sum = 11. 找到可用于求和的最小硬币数量（我们可以使用每种面额的任意数量的硬币）

我搜索了这个硬币变化问题的运行时间复杂度，特别是使用动态编程方法。但无法在任何地方找到解释。

如何计算非动态解决方案的复杂度，然后将其更改为动态解决方案？（不是贪婪的）

编辑：

这是一个要求分析的实现。

public int findCoinChange(int[] coins, int sum,int count) {

    int ret = 0, maxRet = -1;
    if(sum ==0)maxRet = count;
    else if(sum < 0)maxRet = -1;
    else{
        for(int i:coins){
            ret = findCoinChange(coins, sum - i,count+1);
            if(maxRet< 0)maxRet = ret;
            else if(ret >=0 && ret < maxRet){
                    maxRet = ret;
                }
            }
    }
    if(maxRet < 0)return -1;
    else return maxRet;
}

对我来说看起来像组合爆炸。但是我不确定如何为此推断运行时间复杂度。

4

1 回答 1

1

这个问题的动态编程解决方案显然 O(k * n)是（嵌套循环，等等等等），其中k是硬币的数量，并且n是改变的金额。

我不知道您所说的非动态编程解决方案是什么意思。抱歉，您将指定您的意思是什么算法。贪心算法在某些情况下会失败，所以你不应该提到那个。你的意思是线性规划解决方案吗？这是解决这个问题的一种糟糕的方法，因为我们不知道复杂性是什么，并且可以让它任意缓慢地运行。

我也不知道您所说的“将其更改为动态的”是什么意思。

于 2013-06-21T03:52:43.333 回答