java - 使用动态规划改变硬币

Question

换硬币是一个很受欢迎的面试问题。本质上，这个问题意味着给定一组硬币面额和总数，如果每种面额的硬币都有无限供应，那么有多少种方法可以获得总数。

这是我的代码。 逻辑是每次我选择一枚硬币时，问题都会减少到解决总数减去硬币的问题。

public static int numberOfWays(int total, int[] options){

        int[][] memo = new int[options.length][total+1];

        for (int i = 0; i <memo.length ; i++) {

            for (int j = 0; j <memo[i].length ; j++) {

                if(i == 0)  memo[i][j] = 1;
                else if(options[i] > j ) memo[i][j] = memo[i-1][j];
                else memo[i][j] = memo[i-1][j] + memo[i][j - options[i]];
            }
        }
        return memo[options.length-1][total];
    }

这适用于 total = 5 和 options = 1, 2, 3 的测试用例 但失败 total = 10 and options = 2, 5, 3, 6

谁能帮助我理解我做错了什么。

Answer 1

首先，最好写出每个数组元素代表什么的声明:

memo[i][j] represents how many ways to make the total amount j given only coins in denominations options[0], options[1], ..., options[i].

现在，您似乎从中推导出了一些定律:

1. memo[0][j]是1对于所有 j
2. i大于 0，memo[i][j]与memo[i-1][j]相同每当options[i] > j
3. i大于 0，memo[i][j]是memo[i-1][j] + memo[i][j - options[i]]每当options[i] <= j

你的问题是这些定律中的第一个是不正确的。 (后面两个是)

声明“memo[0][j] is 1 for all j”仅在options[0] 时成立是1 .如果options[0]不是 1 , 然后 memo[0][j]当 j 时为 1是 options[0] 的倍数, 如果不是则为 0。仅使用面额硬币 2 ，你赚不到 5 美分，所以你应该有(第二组数据)memo[0][5] == 0 , 但你的程序说 memo[0][5] == 1 .然后，这会抛出所有后续计算。

所以我会修改你的程序说:

            if(i == 0) { if (j % options[i] == 0) memo[i][j] = 1;
                         else memo[i][j] = 0; }
            else if(options[i] > j ) memo[i][j] = memo[i-1][j];
            else memo[i][j] = memo[i-1][j] + memo[i][j - options[i]];

(尽管就纯粹的文体注释而言，我发现 if/else 即使是单个语句也不使用大括号的语句是在询问错误)