题目链接

零钱兑换

题目描述

image.png

实现代码

动态规划思想：记dp[i]表示使用coins数组凑成i金额的最少兑换次数，因此有动态转移方程：

dp[i] = min(dp[i - coins[0], … dp[i-coins[n-1]) + 1

需要注意以下几点:

  1. 初始化条件：

    dp[0] = 0; dp[coins[i]] = 1

  2. 不能兑换的判定（即值为-1的判定）

实现代码：

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  4.         int[] dp = new int[amount + 1];
  5.         int len = coins.length;
  7.         for (int i = 1; i <= amount; i++) {
  8.             int min = Integer.MAX_VALUE;
  9.             boolean can = false;
  10.             for (int j = 0; j < len; j++) {
  11.                 if (i < coins[j]) {
  12.                     continue;
  13.                 }
  14.                 if (i == coins[j]) {
  15.                     min = 0;
  16.                     can = true;
  17.                     break;
  18.                 }
  19.                 if (dp[i - coins[j]] == -1) {
  20.                     continue;
  21.                 }
  22.                 if (min > dp[i - coins[j]]) {
  23.                     min = dp[i - coins[j]];
  24.                     can = true;
  25.                 }
  26.             }
  27.             dp[i] = can ? min + 1 : -1;
  28.         }
  31.         return dp[amount];
  32.     }
  33. }