สมมติว่าเรามีเหรียญมูลค่าต่างกันและจำนวนเงินรวม amount เราต้องกำหนดฟังก์ชันหนึ่งเพื่อคำนวณจำนวนเหรียญน้อยที่สุดที่จำเป็นเพื่อรวมเป็นจำนวนเงินดังกล่าว หากจำนวนเงินนั้นไม่สามารถทำได้จากการรวมเหรียญใดๆ ให้คืนค่า -1 ตัวอย่างเช่น หากอินพุตคือ [1,2,5] และ amount คือ 11 ผลลัพธ์คือ 3 ซึ่งมาจาก 5 + 5 + 1 = 11
ขั้นตอนการแก้ปัญหา
- ถ้า amount = 0 ให้คืนค่า 0
- ถ้าค่าต่ำสุดของอาร์เรย์เหรียญ > amount ให้คืนค่า -1
- กำหนดอาร์เรย์ชื่อ dp ขนาด amount + 1 และเติมด้วย -1
- for i ในช่วงอาร์เรย์เหรียญ
- ถ้า i > ความยาวของ dp - 1 ให้ข้ามไปยังรอบถัดไป
- dp[i] := 1
- for j ในช่วง i + 1 ถึง amount
- ถ้า dp[j - 1] = -1 ให้ข้ามไปยังรอบถัดไป
- อื่นๆ ถ้า dp[j] = -1 ให้ dp[j] := dp[j - i] + 1
- อื่นๆ dp[j] := ค่าต่ำสุดของ dp[j] และ dp[j - i] + 1
- คืนค่า dp[amount]
ตัวอย่าง (Python):
ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
class Solution(object):
def coinChange(self, coins, amount):
if amount == 0:
return 0
if min(coins) > amount:
return -1
dp = [-1 for i in range(0, amount + 1)]
for i in coins:
if i > len(dp) - 1:
continue
dp[i] = 1
for j in range(i + 1, amount + 1):
if dp[j - i] == -1:
continue
elif dp[j] == -1:
dp[j] = dp[j - i] + 1
else:
dp[j] = min(dp[j], dp[j - i] + 1)
return dp[amount]
ob1 = Solution()
print(ob1.coinChange([1,2,5], 11))อินพุต
[1,2,5] 11
เอาต์พุต
3
