โจทย์ทั้งหมด
ปานกลาง 1 ข้อที่แก้แล้ว อัตราผ่าน 100.0%

นับจำนวนวิธีการรวมเหรียญ

นับจำนวนวิธีที่สามารถรวมเหรียญแต่ละชนิดที่กำหนด (มีจำนวนไม่จำกัด) ให้ได้จำนวนเงินที่ต้องการ

สิ่งที่คุณจะได้เรียนรู้

  • นับการจัดหมู่ ไม่ใช่การเรียงสับเปลี่ยน
  • ไล่เหรียญในลูปด้านนอก
  • สร้างอาร์เรย์ DP 1 มิติของจำนวนวิธี

โจทย์

ใช้เหรียญแต่ละชนิดที่กำหนดได้ไม่จำกัดจำนวน เพื่อรวมให้ได้จำนวนเงินที่ต้องการพอดี ให้นับจำนวนวิธีการรวม (combination) โดยไม่สนลำดับการเลือกเหรียญ: การจัดเรียงที่ใช้จำนวนเหรียญแต่ละชนิดเท่ากันถือเป็นวิธีเดียวกัน เหรียญแต่ละชนิดมีมูลค่าต่างกันและเป็นจำนวนเต็มบวก

ให้เขียนฟังก์ชัน coin_sums(amount, coins)

อินพุต

amount: จำนวนเงินรวมที่ต้องการ

coins: มูลค่าเหรียญแต่ละชนิดที่มีให้เลือก (แต่ละชนิดไม่ซ้ำกัน)

เอาต์พุต

คืนค่าจำนวนวิธีการรวมเหรียญแบบไม่เรียงลำดับ

เงื่อนไข

0 ≤ amount ≤ 200 มีเหรียญไม่ซ้ำกัน 0 ถึง 10 ชนิด แต่ละชนิดมีค่าตั้งแต่ 1 ถึง 200 ทุกจำนวนที่เกี่ยวข้องอยู่ในช่วง signed 64-bit จำนวนเงิน 0 มีวิธีเดียวคือไม่เลือกเหรียญเลย

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
amount = 4
coins = [1, 2]

ผลลัพธ์ที่คาดหวัง:
expected = 3
อินพุต:
long long amount = 4;
std::vector<long long> coins = {1, 2};

ผลลัพธ์ที่คาดหวัง:
long long expected = 3;
อินพุต:
long amount = 4;
long[] coins = new long[] {1, 2};

ผลลัพธ์ที่คาดหวัง:
long expected = 3;

คำอธิบาย

วิธีที่เป็นไปได้คือ เหรียญ 1 สี่เหรียญ, เหรียญ 1 สองเหรียญกับเหรียญ 2 หนึ่งเหรียญ, และเหรียญ 2 สองเหรียญ

ตัวอย่างที่ 2
อินพุต:
amount = 3
coins = [2]

ผลลัพธ์ที่คาดหวัง:
expected = 0
อินพุต:
long long amount = 3;
std::vector<long long> coins = {2};

ผลลัพธ์ที่คาดหวัง:
long long expected = 0;
อินพุต:
long amount = 3;
long[] coins = new long[] {2};

ผลลัพธ์ที่คาดหวัง:
long expected = 0;

คำอธิบาย

ผลรวมของเหรียญมูลค่า 2 ทุกแบบจะเป็นเลขคู่ ดังนั้นไม่สามารถรวมเป็น 3 ได้

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

ลำดับของเหรียญไม่สำคัญ จึงต้องนับแบบ combination ตามชนิดเหรียญ ไม่ใช่การเรียงสลับ

คำใบ้ 2

สร้างจำนวนวิธีของแต่ละยอดเงินแบบค่อยเป็นค่อยไป โดยให้แต่ละเหรียญช่วยเติมทุกยอดที่ไปถึงได้

คำใบ้ 3

ระวังยอดเงิน 0 ซึ่งมีวิธีที่ถูกต้องเสมอหนึ่งแบบ: ไม่เลือกเหรียญเลย

ความซับซ้อนที่คาดหวัง

เวลา O(amount × number_of_coins), หน่วยความจำเพิ่ม O(amount)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

# นักโค้ด ภาษา เวลา หน่วยความจำ คะแนนจาก AI คำตอบ
1 ННикита Python 811 ms - 5/5 ดูโค้ด

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

สปอยล์: มีคำตอบเต็ม 1 ข้อด้านล่าง ลองแก้ด้วยตัวเองก่อน คุณยังสามารถดูโค้ดของนักพัฒนาคนอื่นและรีวิว AI ได้ เข้าสู่ระบบและแก้โจทย์เพื่อร่วมพูดคุย