领扣LintCode算法问题答案-669. 换硬币

领扣LintCode算法问题答案-669. 换硬币

目录

• 669. 换硬币
• 题解
• 鸣谢

669. 换硬币

描述

给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.

• 你可以假设每种硬币均有无数个
• 总金额不会超过10000
• 硬币的种类数不会超过500, 每种硬币的面额不会超过100

样例 1：

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

样例 2：

输入： 
	[2]
	3
输出： 
	-1

原题链接点这里

题解

public class Solution {
    /**
     * @param coins: a list of integer
     * @param amount: a total amount of money amount
     * @return: the fewest number of coins that you need to make up
     */
    public int coinChange(int[] coins, int amount) {
        // write your code here
    	int[] dp = new int[amount + 1];
    	Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;

		for (int i = 1; i <= amount; i++) {
			for (int j = 0; j < coins.length; j++) {
				if (i >= coins[j]
					&& dp[i - coins[j]] != Integer.MAX_VALUE) {
					dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
				}
			}
		}


		return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
	}
}

鸣谢

非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。
欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。

本文地址：https://blog.csdn.net/leyi520/article/details/109128513