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

共以下 6 个回答

• kfaebot 普通 2024年5月11日 下午3:49

  class Solution {
  public:
      int coinChange(vector<int>& coins, int amount) {
          //dp[j]表示总金额为j时需要的最少硬币个数
          vector<int> dp(amount+1,INT_MAX);
  
          //初始化
          dp[0]=0;
  
          //状态转移方程
          for(int i=0;i<coins.size();i++){//先遍历物品
              for(int j=coins[i];j<=amount;j++){//再遍历背包
                  if(dp[j-coins[i]]!=INT_MAX){
                      dp[j]=min(dp[j-coins[i]]+1,dp[j]);
                  }
                  else{
                      continue;
                  }
              }
          }
          if(dp[amount]==INT_MAX){
              return -1;
          }
          return dp[amount];
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 王位詮釋 普通 2024年4月14日 下午3:22

  这个题我最开始的时候陷入了一个误区：要凑出来面值为amount，而且同时
  硬币数量还得最少，那就从最大面值的硬币开始分配，这样最后结果就会是
  最小的面值，这种想法本身没问题，但是可能会出现这种情况：一直用最大面值
  硬币匹配导致最后剩下的amount值不足以匹配剩余的硬币，所以这种是有问题的
  class Solution {
      public int coinChange(int[] coins, int amount) {
          //dp[i]表示组成金额i所需要的最少的硬币数量
          //前面凑出来的i的最小的硬币数量可以用来凑后面的i的硬币数量
          //由于后面的i的硬币数量需要依赖前面的i的硬币数量，所以后面的i
          //能凑出来的话dp[i]值一定是小于amount+1的，否则就返回-1
          int[] dp = new int[amount+1];
          Arrays.fill(dp,amount+1);
          dp[0] = 0;
          for(int i=1;i<amount+1;i++){
              for(int j=0;j<coins.length;j++){
                  //防止越界，因为i表示金额值，coins[j]表示第j枚硬币的金额值，i不应该小于coins[j]
                  if(coins[j]<=i){
                      dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
                  }
              }
          }
          return dp[amount]>amount?-1:dp[amount];
      }
  }
  思路：数组dp[i]表示凑出来面值为i时需要的最少的硬币数量；如果面值为i
  的时候前面的都凑不出来，那i的面值肯定也凑不出来，就返回-1；
  否则就动态计算需要的面值，dp[i] = Math.min(dp[i],dp[i-coins[j]]+1)，最后返回结果。
  

  0 赞同 0 条回复

  登录以回复
• heathhou 普通 2024年4月13日 下午3:37

  class Solution {
  public:
      int coinChange(vector<int>& coins, int amount) {
          if(coins.size() <= 0){
              return 0;
          }
  
          int Max = amount + 1;
          // 定义 dp[i] 为组成金额 i 所需最少的硬币数量
          // 初始值设置为需要 amount + 1 的硬币，这是最大值了
          vector<int> dp(amount + 1, Max); 
  
          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 : dp[amount];
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 白雪公主倒拔垂杨柳 永久会员 2024年4月6日 下午3:38

  class Solution {
      public int coinChange(int[] coins, int amount) {
  
          //dp[i]：我们凑成金额为 i 所需要的最少硬币个数为 dp[i];
          int[] dp = new int[amount+1];
          int max=amount+1;
          for(int i=1;i<=amount;i++){
              dp[i]=max;
          }
  
          for(int i=1; i<=amount; i++){
              for(int j=0;j<coins.length;j++){
                  if(i>=coins[j] && dp[i-coins[j]]!=max){
                      dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
                  }
              }
          }
  
          // return dp[amount];
          return dp[amount]==max ?-1:dp[amount];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 云无深雁影 普通 2024年4月5日 上午12:17

  class Solution {
  public int coinChange(int[] coins, int amount) {
  int[] dp = new int[amount + 1];//dp[i]为i元钱的最少硬币数
  for(int i = 0; i < coins.length; i++)
  if(coins[i] < amount + 1)
  dp[coins[i]] = 1;
  dp[0] = 0;
  for(int i = 1; i <= amount; i++){
  boolean finded = false;
  int min = Integer.MAX_VALUE;
  for(int j = 0; j < coins.length;j++){
  if(i – coins[j] >= 0 && dp[i – coins[j]] != -1){
  min = Math.min(min,dp[i – coins[j]] + 1);
  finded = true;
  }
  }
  if(!finded)
  dp[i] = -1;
  else
  dp[i] = min;
  }
  return dp[amount] ;

  }
  

  }
  //时间复杂度On
  //空间复杂度On

  0 赞同 0 条回复

  登录以回复
• 紫芝 普通 2024年4月3日 下午9:46

  思路：dp[i] 表示由 coins 提供的金币组成 总数 amount 使用的最小金币数量，则对于 dp[i] 的值，可以由 min(dp[i], dp[i-coins[j]])得出

  “`c++
  class Solution {
  public:
  int coinChange(vector& coins, int amount) {
  vector dp(amount+1, amount+1);
  dp[0] = 0;
  for (int i=1; i<=amount; i++) { for (int j=0; j amount ? -1 : dp[amount];
  }
  };
  “`

  0 赞同 0 条回复

  登录以回复