Coin Change Dynamic Programming Problem (limited supply of coins)

185 Views Asked by At

I'm trying to solve the coin change problem with the variation that the same coin can be used at most twice. I solved the problem where the coins are unlimited but I still don't quite understand how to do it in case of limited coins.

 function coinChange(coins: number[], amount: number): number[][] {

  let M:number[][] = [];
  for (let i = 0 ; i<coins.length ; i++)
    M[i] = [0];

  for(let i = 0 ; i < coins.length ; i++){
    for(let j = 1 ; j <= amount ; j++){
      if(coins[i] > j && i>0) M[i][j] = M[i-1][j];
      else{
        let diff:number = j-coins[i];
        
        if(M[i][diff] != -1){
          let c:number;
          if(i>0){
            c = Math.min(M[i-1][j],1+M[i][diff]);
          }
          else{ 
            c = 1+M[i][diff];
          }
          M[i][j] = c;
        }
        else M[i][j] = -1;
      }
    }
  }
  return M;
}
1

There are 1 best solutions below

0
Grinza On BEST ANSWER

Solution:

 function coin2(coins:number[], amount:number):number{
  let M:number[][] = [];
  coins.push(...coins)
  for(let i = 0 ; i <= coins.length ; i++){
    M[i] = [];
  }  
  M[0][0] = 0;
  for(let j = 1 ; j <= amount ; j++){
    M[0][j] = Infinity;
  }
  for(let i = 1 ; i <= coins.length ; i++){
    for(let j = 0 ; j <= amount ; j++){
      if(coins[i-1] > j) M[i][j] = M[i-1][j];
      else{
        let dif:number = j-coins[i-1];
        M[i][j] = Math.min(M[i-1][j],1+M[i-1][dif])
      }
    }
  }
  console.log(M);
  return M[coins.length][amount];
}