零钱兑换

322.零钱兑换

题意

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

思路一：完全背包

完全背包：有 $n$ 件物品，背包容量为 $m$ ，每件物品只能使用无限次。

本题翻译过来：有 $n$ 个硬币，每个硬币都可以使用无限次，总金额为 $m$，求组成总金额所需的最少硬币数。

定义 f[i][j]：表示从前 $i$ 个硬币中选一些硬币（可以重复选），满足总金额恰好等于 $j$，最少要选的硬币个数。

考虑第 $i$ 个硬币选或不选：

• 不选：问题变成从前 $i−1$ 个硬币中选一些硬币（可以重复选），满足总金额恰好等于 $j$，最少要选的硬币个数，即 f[i][j] = f[i - 1][j]。

• 选：前提是 $coins[i] ≥ j$。问题变成从前 $i$ 个硬币中选一些硬币（可以重复选），满足总金额恰好等于 $j − coins[i]$，最少要选的硬币个数，即 f[i][j] = f[i][j - coins[i] + 1。注意这里是 $i$ 而不是 $i−1$，因为我们可以重复选第 $i$ 个硬币。

这两种情况取最小值，就得到了答案，即 f[n][amount]。

代码：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] f = new int[n + 1][amount + 1];
        Arrays.fill(f[0], Integer.MAX_VALUE / 2);
        f[0][0] = 0;

        // 这里从 0 开始遍历，整体 i + 1
        for (int i = 0; i < n; i++){
            for (int j = 0; j <= amount; j++){
                if (j < coins[i]) f[i + 1][j] = f[i][j];
                else f[i + 1][j] = Math.min(f[i][j], f[i + 1][j - coins[i]] + 1);
            }
        }

        int res = f[n][amount];
        if (res >= Integer.MAX_VALUE / 2) res = -1;

        return res;
    }
}

思路二：空间优化

因为 f[i] 的状态只与 f[i -1] 有关，所以完全可以只使用两个数组（滚动数组）来优化空间。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] f = new int[2][amount + 1];
        Arrays.fill(f[0], Integer.MAX_VALUE / 2);
        f[0][0] = 0;

        for (int i = 0; i < n; i++) {
            for (int c = 0; c <= amount; c++) {
                if (c < coins[i]) f[(i + 1) % 2][c] = f[i % 2][c];
                else f[(i + 1) % 2][c] = Math.min(f[i % 2][c], f[(i + 1) % 2][c - coins[i]] + 1);
            }
        }

        int ans = f[n % 2][amount];
        return ans < Integer.MAX_VALUE / 2 ? ans : -1;
    }
}

通过观察，可以发现，对于某一个硬币 coins[i]，其 $i$ 是固定的，每一次讨论都只有选与不选两种选择，因此可以将原来的二维数组压缩至一维数组。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        Arrays.fill(f, Integer.MAX_VALUE / 2);
        f[0] = 0;
        
        for (int x : coins) {
            for (int c = x; c <= amount; c++) {
                f[c] = Math.min(f[c], f[c - x] + 1);
            }
        }

        int ans = f[amount];
        return ans < Integer.MAX_VALUE / 2 ? ans : -1;
    }
}