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

共以下 9 个回答

• hi 普通 2023年12月18日 下午6:16

  class Solution {
  public:
      int coinChange(vector<int>& coins, int amount) {
          if(amount < 1) return 0;
  
          vector<int> f(amount + 1, 0x3f3f3f3f);
          f[0] = 0;
  
          for(int i = 1; i <= amount; i++)//从f[1]开始计算到f[amount]
              for(int j = 0; j < coins.size(); j++)//尝试每个硬币值
                  if(i >= coins[j] && f[i - coins[j]] != 0x3f3f3f3f) //注意是&&符号
                      f[i] = min(f[i], f[i - coins[j]] + 1);
  
          if(f[amount] != 0x3f3f3f3f) return f[amount];
          else return -1;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• June 普通 2023年11月16日 下午5:01

  class Solution {
      public int coinChange(int[] coins, int amount) {
          int n = coins.length;
          int[] dp = new int[amount + 1];
          Arrays.fill(dp,amount + 1);
          dp[0] = 0;
          for(int i=0 ; i <= amount ; i++)
          {
              for(int j = 0; j < n ; j++)
              {
                  if(coins[j] <= i) //等于每一个 i-coins[j] 的总金额加一个硬币
                      dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
              }
          }
          return dp[amount] > amount ? -1 : dp[amount];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 北辰 普通 2023年9月15日 上午11:55

  class Solution {
      public int coinChange(int[] coins, int amount) {
          int m = coins.length;
          int n = amount;
          int[] F = new int[n+1];
          Arrays.fill(F,amount+1);
          F[0] = 0;
          for(int i=1;i<=n;i++){
              for(int j=0;j<m;j++){
                  if(i>=coins[j]){
                      //考虑新的硬币组成当前金币为i的数量和原来组成金币i的数量取最小值
                      F[i] = Math.min(F[i],F[i-coins[j]]+1);
                  }
              }
          }
          return F[amount]>amount?-1:F[amount];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Marshan 普通 2023年9月7日 下午8:04

  做过又忘了

  class Solution {
  public:
      int coinChange(vector<int>& coins, int amount) {
  
          vector<int> dp(amount+1,amount+1);
          // dp[i]表示要凑齐i金额需要的最少硬币
  
          dp[0] = 0;
          for(int i = 1;i <= amount;++i){
              for(auto coin:coins){
                  if(i - coin < 0){
                      continue;
                  }
                  dp[i] = min(dp[i],1 + dp[i-coin]);
              }
          }
  
          return dp[amount] != amount + 1 ? dp[amount] : -1;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 人生何处不青山 普通 2023年8月22日 下午11:55

  背包问题

  function coinChange(coins: number[], amount: number): number {
      let dp = new Array(amount + 1).fill(Infinity);
      dp[0] = 0;
      for (let i = 1; i <= amount; i++) {
          for (let coin of coins) {
              if (i >= coin) {
                  dp[i] = Math.min(dp[i], dp[i - coin] + 1);
              }
          }
      }
      return dp[amount] === Infinity ? -1 : dp[amount];
  };
  

  0 赞同 0 条回复

  登录以回复
• Mby 普通 2023年8月21日 下午8:57

  class Solution {
      //动态规划
      public int coinChange(int[] coins, int amount) {
          if(coins.length == 0){
              return -1;
          }
          int[] memo = new int[amount+1];
          memo[0] = 0;
          for(int i = 1; i <= amount; i++){
              int min = Integer.MAX_VALUE;
              for(int j = 0; j < coins.length; j++){
                  if(i - coins[j] >= 0 && memo[i - coins[j]] < min){
                      min = memo[i - coins[j]] + 1;
                  }
              }
              memo[i] = min;
          }
          return memo[amount] == Integer.MAX_VALUE ? -1 : memo[amount];
      }     
  }
  
  

  0 赞同 0 条回复

  登录以回复
• 阿尚 普通 2023年8月10日 下午11:53

  class Solution {
      public int coinChange(int[] coins, int amount) {
          if(amount == 0) return 0;
  
          //dp：装满容量为 j 的背包最少需要 dp[j] 个物品
          int[] dp = new int[amount + 1];
          for(int i = 0; i < dp.length; i++){
              dp[i] = Integer.MAX_VALUE;
          }
          dp[0] = 0;
  
          for(int i = 0; i < coins.length; i++){
              for(int j = coins[i]; j <= amount; j++){
                  if(dp[j - coins[i]] != Integer.MAX_VALUE){
                      dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                  }   
              }
          }
  
          return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• NullPointerException 普通 2023年8月10日 下午8:28

  class Solution {
  public int coinChange(int[] coins, int amount) {
  // 记录每一个金额所需要的硬币 个数 遍历硬币数组 可以取 金额-硬币 或者硬币自身
  int dp[]=new int [amount+1];

      if(amount==0) return 0;
      Arrays.sort(coins);
      Arrays.fill(dp,100000);
      dp[0]=0;
      for(int i=1;i<=amount;i++)
      {
          for(int j=0;j<coins.length;j++)
          {
              if(i-coins[j]>=0)
              {
              dp[i]=Math.min(dp[i-coins[j]]+1,dp[i]);
              }
          }
      }
      if(dp[amount]==100000) return -1;
      return dp[amount];
  
  }
  

  }

  0 赞同 0 条回复

  登录以回复
• 长河呼叫黄江 普通 2023年8月9日 下午11:25

  8.9 周三
  Day30：下面是代码

  class Solution {
      public int coinChange(int[] coins, int amount) {
          int max = amount + 1;
          int[] dp = new int[max];
          Arrays.fill(dp, 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] = Math.min(dp[i], (dp[i - coins[j]] + 1));
              }
          }
          return dp[amount] > amount ? -1 : dp[amount];
      }
  }
  
  

  0 赞同 0 条回复

  登录以回复