【Hot100】LeetCode—322. 零钱兑换

---

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

---

1- 思路

动态规划

动规五部曲

• 1- 定义 dp 数组确定含义
  
  
  
  • dp[j] 代表凑到款项为 j 的最少硬币个数
    
  
  
• 2- 递推公式
  
  
  
  • dp[j] = Math.min(dp[j],dp[amount-]+1)
    
  
  
• 3- 初始化
  
  
  
  • dp[0] = 0
    
  • 其他全部初始化为 max
    
  
  
• 4- 遍历序次
  
  
  
  • 先遍历物品，再遍历背包
    
  • 递推过程需要判断 dp[j - coins] != max
    
  
  

---

2- 实现

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

1. class Solution {
2.     public int coinChange(int[] coins, int amount) {
3.         // 1. 定义 dp 数组
4.         // dp[j] 代表凑到金钱为 j 的最少硬币个数
5.         int[] dp = new int[amount+1];
7.         // 2.递推公式
8.         // dp[j] = Math.min(dp[j],dp[amount-]+1)
9.         
10.         // 初始化
11.         dp[0] = 0;
12.         int max = Integer.MAX_VALUE;
13.         for(int i = 1 ; i <= amount;i++){
14.             dp[i] = max;
15.         }
17.         // 4. 遍历顺序
18.         // 物品
19.         
20.         for(int i = 0 ; i < coins.length;i++){
21.             for(int j = coins[i] ; j <= amount ; j++){
22.                 if(dp[j - coins[i]] != max){
23.                     dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
24.                 }
25.             }
26.         }
28.         if(dp[amount]==max){
29.             return -1;
30.         }
31.         return dp[amount];
32.     }
33. }

复制代码

---

3- ACM 实现

1. public class minCoins {
4.     public static int minCoins(int[] nums,int target){
5.         // 定义 dp
6.         int[] dp = new int[target+1];
8.         // 2. 递推公式
9.         // dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
11.         // 3.初始化
12.         dp[0] = 0;
13.         int max = Integer.MAX_VALUE;
14.         for(int i = 1 ; i <= target;i++){
15.             dp[i] = max;
16.         }
18.         // 4.遍历顺序
19.         for(int i = 0 ; i <nums.length;i++){
20.             for(int j = nums[i]; j<=target;j++){
21.                 if(dp[j-nums[i]] != max){
22.                     dp[j] = Math.min(dp[j],dp[j-nums[i]]+1);
23.                 }
24.             }
25.         }
26.         if(dp[target]==max){
27.             return -1;
28.         }
29.         return dp[target];
30.     }
34.     public static void main(String[] args) {
35.         Scanner sc = new Scanner(System.in);
36.         String input = sc.nextLine();
37.         String[] parts = input.split(" ");
38.         int[] nums = new int[parts.length];
39.         for(int i = 0 ; i < parts.length;i++){
40.             nums[i] = Integer.parseInt(parts[i]);
41.         }
42.         int target = sc.nextInt();
43.         System.out.println("结果是"+minCoins(nums,target));
45.     }
46. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。