leetcode322：零钱兑换
-
题目：
-
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
-
-
思路：动态规划+背包问题；文章来源：https://www.toymoban.com/news/detail-519378.html
- 定义一维数组nums，nums[i] 含义：凑成总金额为i所需的最少硬币个数
-
代码如下：文章来源地址https://www.toymoban.com/news/detail-519378.html
class Solution {
int INF = 0x3f3f3f3f;
public int coinChange(int[] coins, int amount) {
int n = coins.length;
Arrays.sort(coins);
//nums[i] 含义：凑成总金额为i所需的最少硬币个数
int[] nums = new int[amount + 1];
Arrays.fill(nums,INF);
//声明nums[0] = 0,为后面的动态规划做准备
nums[0] = 0;
for ( int i = 1; i <= n; i++ ) {
int coin = coins[i - 1];
for ( int j = coin; j <= amount; j++ ){
nums[j] = Math.min( nums[j], nums[j - coin] + 1 );
}
}
return nums[amount] == INF ? -1 : nums[amount];
}
}
到了这里，关于leetcode322：零钱兑换的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
