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

共以下 1 个回答

• 塔底的仰望 永久会员 2023年9月16日 下午12:05

  dp[i]的定义为amount=i时，所需的最小硬币数量

  class Solution {
      public int coinChange(int[] coins, int amount) {
          int max = amount + 1;
          int[] dp = new int[amount + 1];
          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 条回复

  登录以回复