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

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

乍一看，如果高于剩余值高的硬币在阵列中的位置之前的位置，则您的解决方案看起来会跳过解决方案。考虑n = 5和c = [10,5]的情况。答案应该是1。

在您的代码中，它将到达IF语句检查是否n

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

并将返回0。