LCR 103. 零钱兑换(中等)

Posted on Edited on In Views:

1，问题描述

LCR 103. 零钱兑换

难度：中等

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

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

示例 1：

1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

1
2
输入：coins = [2], amount = 3
输出：-1

示例 3：

1
2
输入：coins = [1], amount = 0
输出：0

示例 4：

1
2
输入：coins = [1], amount = 1
输出：1

示例 5：

1
2
输入：coins = [1], amount = 2
输出：2

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

注意：本题与主站 322 题相同： https://leetcode-cn.com/problems/coin-change/

2，初步思考

​ 动态规划、完全背包问题

​ 模式识别：子问题，可以使用自上而下的递归、自下而上的动态规划

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class _LCR103零钱兑换 {

    Map<Integer, Integer> map = new HashMap<>();

    // 解法：自上而下的递归
    public int coinChange_recursion(int[] coins, int amount) {
        if (amount < 1) return 0;
        if (map.containsKey(amount)) {
            return map.get(amount);
        }
        int min = amount + 1;
        for (int coin : coins) {
            if (coin > amount) {
                continue;
            } else if (coin == amount) {
                map.put(amount, 1);
                return 1;
            } else {// coin小于amount，则尝试使用当前面值coin，即coinChange(coins, amount-coin)
                int cnt = coinChange_recursion(coins, amount - coin);
                if (cnt != -1) min = Math.min(min, cnt + 1);
            }
        }
        map.put(amount, min == amount + 1 ? -1 : min);
        return map.get(amount);
    }

    // 完全背包问题
    // 数量无限，用最少的钱完成目标金额
    // 状态转移方程：dp[i][j] = Math.min(dp[i-1][j], dp[i][j-coin]+1); // 条件dp[i][j-coin]是可行方案！
    // 状态转移方程：dp[i][j] = dp[i-1][j];
    public int coinChange(int[] coins, int amount) {
        int[][] dp = new int[coins.length + 1][amount + 1];
        Arrays.fill(dp[0], amount + 1);
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                int coin = coins[i - 1];
                dp[i][j] = dp[i - 1][j];
                if (j >= coin && dp[i][j - coin] != amount + 1) {// 可以选择这个方案
                    dp[i][j] = Math.min(dp[i][j - coin] + 1, dp[i][j]);
                }
            }
        }
        return dp[coins.length][amount] == amount + 1 ? -1 : dp[coins.length][amount];
    }

    // 一维dp
    public int coinChange_1d(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                int coin = coins[i - 1];
                if (j >= coin && dp[j - coin] != amount + 1) {// 可以选择这个方案
                    dp[j] = Math.min(dp[j - coin] + 1, dp[j]);
                }
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        _LCR103零钱兑换 test = new _LCR103零钱兑换();
//        System.out.println(test.coinChange_recursion(new int[]{1, 2, 5}, 11));
        System.out.println(test.coinChange_recursion(new int[]{2}, 4));
//        System.out.println(test.coinChange_1d(new int[]{1}, 0));
//        System.out.println(test.coinChange_recursion(new int[]{2, 5, 10, 1}, 27));
    }
}