网站建站管理系统360搜索首页

1.题目描述

2.思路

这里面钱币的数量是无限的。
装满这个背包（总金额）要用多少容量（硬币数量）。
（1）确定dp数组的含义
（2）装满容量为j，最少的物品为dp[j],要求硬币数量dp[amount]
(3)dp[0]=0
(4)不管是排列还是组合，这道题都是要装满背包。
格式：
for（物品） for（背包）-》组合数
for（背包）for（物品）-》排列数

3.代码实现

class Solution {public int coinChange(int[] coins, int amount) {int max = Integer.MAX_VALUE - 1;int[] dp = new int[amount + 1];for (int i = 1; i <= amount; i++) {dp[i] = max;}dp[0] = 0;for (int i = 1; i <= amount; i++) { // 遍历金额for (int j = 0; j < coins.length; j++) { // 遍历硬币if (coins[j] <= i && dp[i - coins[j]] != max) {dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);}}}return dp[amount] == max ? -1 : dp[amount];}
}