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