【陪伴式刷题】Day 39｜动态规划｜518. 零钱兑换 II（Coin Change II）

刷题顺序按照代码随想录建议

题目描述

英文版描述

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

Input: amount = 5, coins = [1,2,5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] Output: 1

Constraints:

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• All the values of coins are unique.
• 0 <= amount <= 5000

英文版地址

leetcode.com/problems/co…

中文版描述

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

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入： amount = 5, coins = [1, 2, 5] 输出： 4 解释： 有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1

示例 2：

输入： amount = 3, coins = [2] 输出： 0 解释： 只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

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

提示：

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• coins 中的所有值 互不相同
• 0 <= amount <= 5000

中文版地址

leetcode.cn/problems/co…

解题方法

class Solution {
    public int change(int amount, int[] coins) {
        // dp[i][j] 表示由[0,i]中的硬币正好装满容积为j的背包共有dp[i][j]种方法
        int[][] dp = new int[coins.length][amount + 1];
        if (coins.length == 1) {
            if (amount % coins[0] == 0) {
                return 1;
            } else {
                return 0;
            }
        }
        // 初始化
        for (int j = 0; j < amount + 1; j++) {
            if (j % coins[0] == 0) {
                dp[0][j] = 1;
            }
        }
        for (int i = 0; i < coins.length; i++) {
            dp[i][0] = 1;
        }
        // 遍历顺序
        for (int i = 1; i < coins.length; i++) {
            for (int j = 0; j < amount + 1; j++) {
                if (j >= coins[i]) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[coins.length - 1][amount];
    }
}

复杂度分析

• 时间复杂度：O(n*amount)，其中 amount是总金额，n 是数组 coins 的长度
• 空间复杂度：O(n*amount)