Cộng thành số tiền với ít đồng xu nhất trong JavaScript

Mô tả vấn đề

Chúng ta cần viết hàm JavaScript nhận vào mảng arr làm đối số đầu tiên - các mệnh giá đồng xu. Đối số thứ hai là số amount - số tiền cần đạt. Hàm trả về số đồng xu tối thiểu để đạt amount. Nếu không thể, trả về -1.

Ví dụ, nếu đầu vào là:

const arr = [1, 2, 5]; 
const amount = 17;

Thì đầu ra nên là:

const output = 4;

Giải thích đầu ra

Vì 17 = 3*5 + 1*2 (4 đồng xu).

Ví dụ minh họa

Mã thực hiện (quy hoạch động bottom-up):

const arr = [1, 2, 5]; 
const amount = 17; 
const minCoins = (arr = [], amount = 1) => { 
  const changes = []; 
  changes[0] = 0; 
  while(changes.length <= amount){ 
    let change = Math.pow(2, 31) - 1; 
    for (let i = 0; i < arr.length; i++) { 
      if (changes.length - arr[i] < 0){ continue; }; 
      change = Math.min(change, 1 + changes[changes.length - arr[i]]); 
    }; 
    changes.push(change); 
  }; 
  return changes[amount] == Math.pow(2, 31) - 1 ? -1 : changes[amount]; 
}; 
console.log(minCoins(arr, amount));

Đầu ra

Kết quả trong console sẽ là:

4