零钱兑换

[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;
};