题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

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

题目分析

动态规划
设 ans[i] 为组成总金额 i 的最少硬币数量，则 ans[i] = ans[i – 某个硬币面额] + 1，枚举所有面额后取最小值。

时间复杂度 O(m * n)，m为硬币种类，n为总金额

Java

public int coinChange(int[] coins, int amount) {
    int MAX = amount + 1;
    int[] ans = new int[amount + 1];
    for (int i = 1; i <= amount; i++) {
        ans[i] = MAX;
        for (int coin : coins) {
            if (coin <= i) {
                int pre = ans[i - coin];
                ans[i] = Math.min(ans[i], pre + 1);
            }
        }
    }
    return ans[amount] == MAX ? -1 : ans[amount];
}

Kotlin

fun coinChange(coins: IntArray, amount: Int): Int {
    val ans = IntArray(amount + 1)
    val MAX = amount + 1
    for (i in 1..amount) {
        ans[i] = MAX
        for (c in coins) {
            if (c <= i) {
                ans[i] = min(ans[i], ans[i - c] + 1)
            }
        }
    }
    return if (ans[amount] == MAX) -1 else ans[amount]
}