322.零钱兑换

力扣题目链接

题目

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

思路

典型的完全背包问题，硬币是物品，要凑的金额是背包，求装满背包最少的物品件数

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

用数组dp[j]表示凑出j所需硬币最少数量，j表示要凑出的金额。
变量用j而不是i是因为i通常用来遍历数组元素。

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];
    }
}