518.零钱兑换 II

力扣题目链接

题目

给你一个整数数组 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

提示：

• coins中的所有值互不相同

思路

1. 确定dp数组及下标含义

用数组dp[j]表示凑出总金额j的硬币组合数。

2. 递推公式

数组中的每个硬币，都可能采用也可能不采用, 采用某个硬币可记为coins[i]。
j - coins[i]所需的硬币最少数量为dp[j - coins[i]], 在此基础上再加上一个硬币coins[i]即dp[j - coins[i]] + 1 就可以得到dp[j]。
但是采用的coins[i]具体为哪个，需要遍历每个元素，求最小值。

所以递推公式为：dp[j] = min(dp[j - coins[i]] + 1)

3. dp数组初始化

当要凑出的金额为0时，很明显dp[0] = 0。
数组中的其他元素初始值该为多少？我们要求的是最小值，所以可以初始化一个比较大的值表示无穷大，在比较过程中会把大值淘汰掉。
多大合适呢？最好的办法为j + 1，因为要凑出j，不可能用j + 1个硬币。
所以初始化dp[j] = j + 1

4. 确定遍历顺序

本题求最小个数，有无顺序都不影响最小个数。 外层循环遍历dp，问题规模从小到大；内层循环遍历数组，遍历每个元素求最小值。

算法描述

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 定义dp数组
        int[] dp = new int[amount + 1];
        // 初始化dp数组
        dp[0] = 0;
        for (int j = 1; j < dp.length; j++) {
            dp[j] = j + 1;
        }
        // 外层遍历背包
        for (int j = 1; j <= amount; j++) {
            // 内层遍历物品
            for (int coin : coins) {
                // 前序有解才可以
                if (j >= coin && dp[j - coin] != j - coin + 1) {
                    dp[j] = Math.min(dp[j], dp[j - coin] + 1);
                }
            }
        }
        // dp[amount] = amount + 1 表示无解
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}