สมมุติว่าเรามีเหรียญหลายนิกายและจำนวนเงินรวม เราต้องกำหนดหนึ่งฟังก์ชันเพื่อคำนวณจำนวนเหรียญน้อยที่สุดที่เราต้องใช้ในการคำนวณจำนวนนั้น เมื่อเงินจำนวนนั้นไม่สามารถใช้ร่วมกับเหรียญได้ ให้คืน -1 ดังนั้นหากอินพุตคือ [1,2,5] และจำนวนคือ 11 ผลลัพธ์จะเป็น 3 ซึ่งสร้างโดยใช้ 5 + 5 + 1 =11
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ถ้าจำนวน =0 ให้คืนค่า 0
- ถ้าขั้นต่ำของอาร์เรย์เหรียญ> จำนวน แล้วคืน -1
- กำหนดหนึ่งอาร์เรย์ที่เรียกว่า dp จำนวนขนาด + 1 และเติมด้วย -1
- สำหรับฉันในอาร์เรย์เหรียญช่วง
- ถ้า i> ความยาวของ dp – 1 จากนั้นข้ามส่วนถัดไป ไปที่การทำซ้ำครั้งต่อไป
- dp[i] :=1
- สำหรับ j ในช่วง i + 1 ถึงจำนวน
- ถ้า dp[j – 1] =-1 จากนั้นข้ามส่วนถัดไป ไปที่การทำซ้ำครั้งต่อไป
- มิฉะนั้น ถ้า dp[j] =-1 แล้ว dp[j] :=dp[j - i] + 1
- มิฉะนั้น dp[j] :=ขั้นต่ำของ dp[j] และ dp[j – i] + 1
- คืน dp[จำนวน]
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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) #print(dp) return dp[amount] ob1 = Solution() print(ob1.coinChange([1,2,5], 11))
อินพุต
[1,2,5] 11
ผลลัพธ์
3
