零钱兑换

[pwstrick]

322. 零钱兑换

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    if(amount == 0)
        return 0;
   let len = coins.length,
    min = Number.MAX_VALUE,
    dp = [new Array(amount)];
  for (let j = 1; j <= amount; j++) {   //初始化第一行
    dp[0][j] = (coins[0] > j || (j % coins[0]) > 0) ? 0 : (j / coins[0]);
  }
  for (let i = 1; i < len; i++) {
    dp[i] = [];
    for (let j = 1; j <= amount; j++) {
      let rest = j - coins[i];
      if(rest == 0) {       //
        dp[i][j] = 1;
        continue;
      }
      if(rest < 0) {
        dp[i][j] = dp[i-1][j];
        continue;
      }
      if(dp[i-1][j] > 0 && dp[i][rest] > 0) {
        dp[i][j] = Math.min(dp[i-1][j], dp[i][rest] + 1);
      }else if(dp[i-1][j] > 0) {
        dp[i][j] = dp[i-1][j];
      }else if(dp[i][rest] > 0) {
        dp[i][j] = dp[i][rest] + 1;
      }else {
        dp[i][j] = 0;
      }
    }
  }
  for(let i = 0; i < len; i++) {
    if(dp[i][amount] == 0) {
      continue;
    }
    if(dp[i][amount] > 0) {
      min = Math.min(min, dp[i][amount]);
    }
  }
  return min == Number.MAX_VALUE ? -1 : min;
};