algorithm - 硬币变化分析

Question

{1,3,5}面额硬币；总和 = 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;
}

在我看来就像组合爆炸。但是我不确定如何为此推断出运行时复杂性。

Answer 1

dynamic programming solution这个问题很明显 O(k * n)(嵌套循环，blah blah blah)其中k是硬币的数量，n 是找零的金额。

我不知道你所说的非动态规划解决方案是什么意思。抱歉，您将必须指定您的意思是什么算法。 greedy algorithm fails在某些情况下，您不应该指的是那个。你的意思是线性规划解决方案？对于这个问题，这是一个糟糕的方法，因为我们不知道复杂性是什么，并且有可能让它以任意慢的速度运行。

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