2020-11-12--数据结构与算法-14(动态规划篇3)

凑零钱问题

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:
 * Date: 2020-11-11
 * Time: 22:16
 * 先看下题目：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，
 * 每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚
 * 硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：
 * <p>
 * <p>
 * coins 中是可选硬币面值，amount 是目标金额
 * int coinChange(int[] coins, int amount);
 * <p>
 * k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
 */
public class MakeTheChange {
    //较好的说明
    //最后一个硬币是1的话，最少硬币数应该为【组成10的最少硬币数】+ 1枚（1块硬币）
    //最后一个硬币是2的话，最少硬币数应该为【组成9的最少硬币数】+ 1枚（2块硬币）
    //最后一个硬币是5的话，最少硬币数应该为【组成6的最少硬币数】+ 1枚（5块硬币）

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11));
    }

    public static int coinChange(int[] coins, int amount) {
        //首先判断数组的容量和金额大小
        if (coins.length <= 0 || amount < 0) {
            return -1;
        }
        if (amount ==0){return 0;}
        //考虑建立一个数组存放每个状态的值,表示dp[i] 要取出金额为i 需要的金币的最小的数量
        int[] dp = new int[amount + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[0] = 0;
            dp[i] = 99999;
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
                }
            }
        }
        int result = dp[amount] == 99999 ? -1:dp[amount];
        return result;
    }
}