หาจำนวนเหรียญน้อยที่สุดเพื่อให้ได้จำนวนเงินที่ต้องการใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับ arr เป็นอาร์กิวเมนต์แรก อาร์เรย์นี้ระบุประเภทของเหรียญที่เรามี

อาร์กิวเมนต์ที่สองคือตัวเลข amount ซึ่งระบุจำนวนเงินที่เราต้องการรวมกัน ฟังก์ชันควรคืนค่าจำนวนเหรียญน้อยที่สุดที่ใช้รวมได้จำนวนเงินดังกล่าว

หากไม่สามารถทำได้เลย ให้คืนค่า -1

ตัวอย่างเช่น หากอินพุตคือ

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

ผลลัพธ์ควรเป็น

const output = 4;

คำอธิบายผลลัพธ์:

เพราะจำนวนเงินสามารถทำได้จากเหรียญ 5 บาท 3 เหรียญ และเหรียญ 2 บาท 1 เหรียญ

ตัวอย่างโค้ด

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

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็น

4