小编arp*_*tam的帖子

{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;
}

看起来像Combinatorial爆炸给我.但是,我不确定如何推断运行时间的复杂性.