Search code examples
javascripttypescriptdynamic-programmingcoin-change

Coin Change Dynamic Programming Problem (limited supply of coins)


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

Solution

  • 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];
    }