【动态规划专题】LeetCode 322. 零钱兑换

共以下 3 个回答

• 陆狗陆狗 普通 2025年1月8日 上午9:11

  解题思路
  – dp[i]表示金额为amount的最少组合次数
  – dp[i]和dp[i-coins]的关系，主要是看coins里面有哪些硬币。取最小的+1即可。
  – 比如conins的范围是[2,3,5]
  – 那么dp[i] 就是 Math.min(dp[i-2],dp[i-3],dp[i-5])+1
  【题解1】没参考题解的思路，时间复杂度是O(m*n)

  class Solution {
      public int coinChange(int[] coins, int amount) {
          // dp[i]表示金额为amount的最少组合次数
          // dp[i]和dp[i-coins]的关系，主要是看coins里面有哪些硬币。取最小的+1即可。但是要注意-1的场景判断
          // 之所以要+1，是因为amount从0
          int[] dp = new int[amount + 1];
          // 【错误】coins不是顺序的，进行一下排序
          Arrays.sort(coins);
          // 【错误】没有提前赋值
          // 金额为0，那么只需要0个硬币
          dp[0] = 0;
  
          for (int amountValue = 1; amountValue <= amount; amountValue++) {
              // 初始值
              if (amountValue < coins[0]) {
                  dp[amountValue] = -1;
                  // 【错误】没有提前返回
                  continue;
              }
  
              // 分情况判断
              int target = -1;
              for (int j = 0; j < coins.length; j++) {
                  // 【错误】没有判断是否已经越界
                  int preAmountValue = amountValue - coins[j];
                  if (preAmountValue < 0) {
                      break;
                  }
                  int preDp = dp[preAmountValue];
                  if (preDp != -1) {
                      target = target == -1 ? preDp + 1 : Math.min(target, preDp + 1);
                  }
              }
              dp[amountValue] = target;
          }
          return dp[amount];
  
      }
  }
  

  • 错误点1：coins不是顺序的，进行一下排序
  • 错误点2：没有提前赋值给dp[0]=0
  • 错误点3：一些初始值没有提前返回
  • 错误点4：没有判断是否已经越界

  题解2

  class Solution {
      public int coinChange(int[] coins, int amount) {
          // dp[i]表示金额为i的最少硬币数
          int[] dp = new int[amount + 1];
  
          // 初始化
          for (int i = 1; i <= amount; i++) {
              dp[i] = Integer.MAX_VALUE; // 将所有金额初始化为一个较大的值
          }
          dp[0] = 0; // 凑成金额0需要0个硬币
  
          // 动态规划计算最少硬币数
          for (int i = 1; i <= amount; i++) {
              for (int coin : coins) {
                  if (i >= coin) {
                      int preDp = dp[i - coin];
                      if (preDp != Integer.MAX_VALUE) { // 只有在可达的情况下才更新
                          dp[i] = Math.min(dp[i], preDp + 1);
                      }
                  }
              }
          }
  
          // 如果dp[amount]仍然是初始值，表示无法凑成该金额
          return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Aatorx 永久会员 2024年12月25日 下午4:58

  class Solution {
  public:
      int coinChange(vector<int>& coins, int amount) {
          vector<int> dp(amount + 1, amount + 1);
          dp[0] = 0;
          for(int i = 1; i <= amount; i++) {
              for(int j = 0; j < coins.size(); j++) {
                  if(coins[j] <= i) {
                      dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                  }
              }
          }
          return dp[amount] == amount + 1 ? -1 : dp[amount];
      }
  };
  

  时间复杂度O(N∗M)，空间复杂度O(N)。

  0 赞同 0 条回复

  登录以回复
• 秋山丽奈 普通 2024年12月24日 下午9:04

  思路：递归+记忆化

  class Solution {
  
      int[] memo;
      public int coinChange(int[] coins, int amount) {
          if(amount == 0){
              return 0;
          }
          this.memo = new int[amount];
          Arrays.sort(coins);
          Arrays.fill(this.memo, -1);
          int ans = dfs(coins, amount); 
          return ans > 0 && ans != Integer.MAX_VALUE/2 ? ans:-1;     
      }
  
      int dfs(int[] coins, int amount){
          if(amount < 0){
              return -1;
          }
  
          if(amount == 0){
              return 0;
          }
  
          if(this.memo[amount-1] != -1){
              return this.memo[amount-1];
          }
  
          int current = Integer.MAX_VALUE / 2;
          for(int i = coins.length-1; i >= 0; i --){
              int temp = dfs(coins, amount-coins[i]);
              if(temp >= 0){
                  current = Math.min(current, temp+1);
              }
          }
  
          this.memo[amount-1] = current ;
          return current;
  
      }
  }
  

  0 赞同 0 条回复

  登录以回复