---

题目

• 原题连接：322. 零钱兑换

---

1- 思路

思路

• 其中 amount 是背包容量 ——> 其中 nums 数组代表的背包重量

---

2- 实现

⭐322. 零钱兑换——题解思路

class Solution {public int coinChange(int[] coins, int amount) {//1.定义dp数组int[] dp = new int[amount+1];// 2. 定义递推公式// dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);// 3. 初始化int max = Integer.MAX_VALUE;for(int i = 0 ; i < amount+1;i++){dp[i] = max;}dp[0] = 0;// 4. 遍历// 先遍历物品 再遍历背包for(int i = 0 ;i < coins.length;i++){for(int j = coins[i] ; j<=amount;j++){if (dp[j - coins[i]] != max) {//选择硬币数目最小的情况dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}}return dp[amount]==max? -1:dp[amount];}
}

---

3- ACM 实现

public class moneyChange {public static int moneyChange(int[] coins,int amount){//1.定义dp数组int[] dp = new int[amount+1];//2.递推公式// dp[j] = (dp[j-coins[i]]+1,dp[j]);//3.初始化int max = Integer.MAX_VALUE;for(int i = 0 ; i < dp.length;i++){dp[i] = max;}dp[0] = 0;//4. 遍历顺序for(int i = 0 ; i < coins.length;i++){for (int j = coins[i] ; j <=amount;j++){if(dp[j-coins[i]]!=max){dp[j] = Math.min(dp[j-coins[i]]+1,dp[j]);}}}return dp[amount]==max? -1:dp[amount];}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入数组长度");int n = sc.nextInt();int[] coins = new int[n];for (int i = 0 ; i < n;i++){coins[i] = sc.nextInt();}System.out.println("输入amount");int amount = sc.nextInt();System.out.println("结果是"+moneyChange(coins,amount));}
}

---