硬币变化动态规划问题(硬币供应有限)

Question

我试图解决硬币变化的问题，相同的硬币最多可以使用两次。我解决了硬币无限的问题，但我仍然不太明白在硬币有限的情况下该怎么做。

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

Answer 1

解决方案:

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