สมมุติว่าเรามีรายการตัวเลขที่เรียกว่า nums ที่แทนราคาหุ้นของบริษัทหนึ่งๆ ตามลำดับเวลาและเรายังมีค่า k อีกค่าหนึ่งด้วย เราต้องหากำไรสูงสุดที่เราสามารถทำได้จากการซื้อและขายสูงสุด k (เราต้องซื้อ) ก่อนขายและขายก่อนซื้อ)
ดังนั้น หากอินพุตเป็นเหมือนราคา =[7, 3, 5, 2, 3] k =2 แล้วผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถซื้อที่ 3 แล้วขายที่ 5 ซื้ออีกครั้งที่ 2 แล้วขาย ที่ 3.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i, k, ซื้อแล้ว
- ถ้าฉันเท่ากับขนาดของราคาหรือ k เท่ากับ 0 แล้ว
- คืน 0
- ถ้าซื้อจริงก็
- ผลตอบแทนสูงสุดของ (dp(i+1, k-1, False) + ราคา[i]) และ dp(i+1, k, ซื้อแล้ว)
- มิฉะนั้น
- ผลตอบแทนสูงสุดของ (dp(i+1, k, True) - ราคา[i]) และ dp(i + 1, k, ซื้อแล้ว)
- จากการเรียกเมธอดหลัก dp(0, k, False) และส่งคืนผลลัพธ์
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution: def solve(self, prices, k): def dp(i, k, bought): if i == len(prices) or k == 0: return 0 if bought: return max(dp(i + 1, k - 1, False) + prices[i], dp(i + 1, k, bought)) else: return max(dp(i + 1, k, True) - prices[i], dp(i + 1, k, bought)) return dp(0, k, False) ob = Solution() prices = [7, 3, 5, 2, 3] k = 2 print(ob.solve(prices, k))
อินพุต
[7, 3, 5, 2, 3], 2
ผลลัพธ์
3
