On this page

ข้อ 65 · LC714 Best Time to Buy and Sell Stock with Transaction Fee (หุ้นมีค่าธรรมเนียม) 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

หากำไรสูงสุดจากการซื้อขายหุ้นไม่จำกัดครั้งแต่มี transaction fee ด้วย DP สอง state ถือ/ไม่ถือ

โจทย์ (LC714): กำหนด array (ลิสต์) จำนวนเต็ม prices โดย prices[i] คือราคาหุ้นในวันที่ i และจำนวนเต็ม fee ที่แทนค่าธรรมเนียมการทำธุรกรรมมา ให้หากำไร maximum ที่ทำได้ ทำธุรกรรมได้ไม่จำกัดจำนวนครั้ง แต่ต้องขายหุ้นที่ถืออยู่ก่อนจึงจะซื้อใหม่ได้อีกครั้ง (ห้ามถือหุ้นหลายรอบซ้อนกันพร้อมกัน) และเสีย fee เพียงครั้งเดียวต่อหนึ่งรอบการซื้อขาย

Example 1

Input:: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output:: 8
Explanation:: ซื้อที่ prices[0]=1 ขายที่ prices[3]=8 กำไร (8-1)-2 = 5 แล้วซื้อที่ prices[4]=4 ขายที่ prices[5]=9 กำไร (9-4)-2 = 3 รวม 5+3 = 8

Example 2

Input:: prices = [1, 3, 7, 5, 10, 3], fee = 3
Output:: 6

Constraints (ข้อจำกัด)

1 <= prices.length <= 5 × 10^4
1 <= prices[i] < 5 × 10^4
0 <= fee < 5 × 10^4

แนวทาง — ต้องใช้อะไร & คิดยังไง

state (สถานะ) มีสองมิติ: วันที่ i และ state ว่าตอนนี้ถือหุ้นอยู่หรือไม่ (dp[i][ถือ/ไม่ถือ]) เพราะแต่ละวันใช้แค่คำตอบของวันก่อนหน้า เราจึงยุบมิติวันให้เหลือค่าปัจจุบัน ใช้สองตัวแปร: cash (กำไรมากสุดเมื่อวันนี้ไม่ถือหุ้น) กับ hold (กำไรมากสุดเมื่อวันนี้ถือหุ้นอยู่)

ถ้าลองคิดแบบ greedy (โลภ) ว่าเจอราคาต่ำก็ซื้อ ราคาสูงก็ขาย จะพลาดเพราะ fee ทำให้บางรอบซื้อขายไม่คุ้ม ต้องให้ DP ชั่งน้ำหนักทุกวันว่าการเปลี่ยน state คุ้มกว่าการอยู่เฉยไหม

initialize วันแรก: cash = 0 (ยังไม่ถือ ไม่มีกำไร), hold = -prices[0] (ซื้อวันแรก จ่ายเงินไปแล้ว)
iterate ราคาตั้งแต่วันที่สองเป็นต้นไป
update cash: อยู่เฉย (cash เดิม) หรือขายหุ้นที่ถืออยู่ (hold + price - fee) เลือกมากกว่า
update hold: ถืออยู่แล้ว (hold เดิม) หรือเพิ่งซื้อวันนี้ (cash - price) เลือกมากกว่า
return cash (จบเกมต้องไม่ถือหุ้น)

จุดพลาดที่พบบ่อย

คำตอบสุดท้ายต้องอ่านจาก cash ไม่ใช่ hold เพราะการจบเกมโดยยังถือหุ้นค้างไว้ไม่ใช่กำไรจริง (ยังไม่ได้ขายเป็นเงิน) และหัก fee ที่เดียวให้สม่ำเสมอ (เฉลยนี้หักตอนขาย) อย่าหักทั้งตอนซื้อและตอนขาย

ไล่ทีละสเต็ป

iterate prices = [1,3,2,8], fee = 2 (เริ่ม cash=0, hold=-1):

price	cash ใหม่ = max(cash, hold+price-fee)	hold ใหม่ = max(hold, cash-price)
3	max(0, -1+3-2) = 0	max(-1, 0-3) = -1
2	max(0, -1+2-2) = 0	max(-1, 0-2) = -1
8	max(0, -1+8-2) = 5	max(-1, 0-8) = -1
จบ	คืน cash = 5	-

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

def max_profit(prices, fee):
    cash = 0             # กำไรมากสุดเมื่อ "ไม่ถือ" หุ้น (เริ่มวันแรก)
    hold = -prices[0]    # กำไรมากสุดเมื่อ "ถือ" หุ้น (ซื้อวันแรก จ่ายไปแล้ว)
    for price in prices[1:]:
        # วันนี้ไม่ถือ: อยู่เฉย ๆ หรือ ขายหุ้นที่ถืออยู่ (จ่าย fee ตอนขาย)
        cash = max(cash, hold + price - fee)
        # วันนี้ถือ: ถืออยู่แล้ว หรือ เพิ่งซื้อวันนี้ด้วยเงิน cash
        hold = max(hold, cash - price)
    return cash          # จบเกมต้องไม่ถือหุ้น กำไรจึงอยู่ที่ cash

print(max_profit([1, 3, 2, 8, 4, 9], 2))  # 8
print(max_profit([1, 3, 7, 5, 10, 3], 3)) # 6

Output

8
6

แม้เขียนด้วยตัวแปรสองตัว แต่แท้จริงนี่คือ 2D DP dp[i][ถือ/ไม่ถือ] แค่ยุบมิติวัน (i) ให้เหลือค่าปัจจุบัน เพราะแต่ละวันใช้แค่คำตอบของวันก่อนหน้า transition ของ cash คือ วันนี้ไม่ถือ ได้จากเมื่อวานก็ไม่ถือ (อยู่เฉย) หรือเมื่อวานถือแล้ววันนี้ขาย (บวก price ลบ fee) ส่วน hold คือ วันนี้ถือ ได้จากเมื่อวานก็ถือ หรือวันนี้เพิ่งซื้อ (เอา cash เมื่อวานมาลบ price)

ข้อสังเกตเล็ก ๆ: บรรทัด hold ใช้ cash ที่เพิ่ง update ในบรรทัดบน แต่ก็ยังถูกต้อง เพราะการซื้อในวันเดียวกับที่เพิ่งขายไม่ได้ให้กำไรเพิ่ม (การขายแล้วซื้อทันทีที่ราคาเดิมไม่เปลี่ยนอะไร) จึงไม่กระทบคำตอบ เราหัก fee ตอนขายเพียงครั้งเดียวต่อรอบ

Time O(n) iterate ราคาครั้งเดียว · Space O(1) ใช้สองตัวแปรแทน table เต็ม

💡 สรุป pattern

โจทย์ที่แต่ละ step มีชุด state จำกัด (เช่น ถือ/ไม่ถือหุ้น) ให้ตั้งตัวแปรหนึ่งตัวต่อ state แล้ว update ทุกก้าวจากค่าก่อนหน้า — นี่คือแม่แบบของโจทย์ตระกูล Best Time to Buy and Sell Stock ทั้งหมด