这种硬币兑换问题的解决方案有什么问题？

Question

这是hackerrank（https://www.hackerrank.com/challenges/coin-change）的硬币更换问题。它要求计算使用给定面值的硬币对N进行更改的方法总数。

例如，有四种方法可以使用面额为1、2和3的硬币兑换4。它们是-{1,1,1,1}，{1,1,2}，{2,2}，{1,3}

我尝试过在java中使用动态编程实现递归解决方案。我的解决方案是基于这样一个想法，对于给定面额的每一枚硬币，我们反复观察是否可以通过选择硬币来达到总数。如果选择当前的硬币导致解决方案，我们更新的方式总数。但是解决方案不起作用。

下面是实现

public static long getWays(long n, long[] c) {
        Map<String, Long> map = new HashMap<String, Long>();
        return fun(n, c, 0, map);
    }
public static long fun(long n, long[] c, int i, Map<String, Long> memo){
    if(n == 0) return 1;
    if(i >= c.length) return 0;
    if(n < c[i]) return 0;
    String key = n + "_" + i;
    if(memo.containsKey(key)) return memo.get(key);
    long ways = fun(n, c, i+1, memo) + fun(n-c[i], c, i, memo);
    memo.put(key, ways);
    return ways;
}

这给了我错误的答案。例如，有5种方法可以使用{2,5,3,6}的硬币对10进行更改，但它返回4作为输出。

我哪里错了？




Answer 1

乍一看，如果高于剩余值的硬币位于数组中第i个位置之前，您的解决方案似乎会跳过解决方案。考虑n=5和c=[10,5]的情况。答案应该是1。

在代码中，它将进入if语句检查if n

if(n < c[i]) return 0;

将返回0。