ปัญหา: กำหนด Stock Prices `prices[i]` และ Max Transactions `k` หา Max Profit จาก ≤ k Buy-Sell Pairs (ต้อง Buy ก่อน Sell, Sell ก่อน Buy ถัดไป)
อัลกอริทึม: DP Top-Down with Memoization
State: `dp(i, k, holding)` = Max Profit จาก Day i ถึง สิ้นสุด กับ k Transactions เหลือ และ Holding Stock หรือไม่
- `i`: Current Day Index
- `k`: Remaining Transactions (แต่ละ Sell = 1 Transaction)
- `holding`: 0=ไม่ถือหุ้น, 1=ถือหุ้นอยู่
Recurrence
dp(i, k, holding):
if i == n or k == 0: return 0
if holding:
# Option 1: Sell Today → Profit + prices[i], k-1, not holding
# Option 2: Hold → dp(i+1, k, True)
return max(prices[i] + dp(i+1, k-1, False), dp(i+1, k, True))
else:
# Option 1: Buy Today → Profit - prices[i], holding
# Option 2: Skip → dp(i+1, k, False)
return max(-prices[i] + dp(i+1, k, True), dp(i+1, k, False))
การติดตั้ง (Top-Down Memoization)
from functools import lru_cache
class Solution:
def solve(self, prices, k):
n = len(prices)
@lru_cache(None)
def dp(i, k, holding):
if i == n or k == 0:
return 0
if holding:
return max(
prices[i] + dp(i + 1, k - 1, False), # Sell
dp(i + 1, k, True) # Hold
)
else:
return max(
-prices[i] + dp(i + 1, k, True), # Buy
dp(i + 1, k, False) # Skip
)
return dp(0, k, False)
# Test
ob = Solution()
prices = [7, 3, 5, 2, 3]
k = 2
print(ob.solve(prices, k)) # 3 (Buy 3 Sell 5, Buy 2 Sell 3)
คำอธิบาย
State `(i, k, holding)` Memoized ด้วย `@lru_cache`
Base Case: หมดวัน หรือหมด Transactions → Profit 0
Holding=True: เลือก Sell (ใช้ 1 Transaction) หรือ Hold
Holding=False: เลือก Buy หรือ Skip
Start: Day 0, k Transactions, Not Holding
Complexity
- States: n × k × 2
- Time: O(n × k)
- Space: O(n × k) Memoization
Optimization: Bottom-Up DP (O(nk) Time, O(k) Space)
def solve_bottom_up(prices, k):
n = len(prices)
if k >= n // 2: # Unlimited Transactions
return sum(max(0, prices[i+1] - prices[i]) for i in range(n-1))
# buy[j] = max profit after j-th buy
# sell[j] = max profit after j-th sell
buy = [float('-inf')] * (k + 1)
sell = [0] * (k + 1)
for price in prices:
for j in range(1, k + 1):
buy[j] = max(buy[j], sell[j-1] - price)
sell[j] = max(sell[j], buy[j] + price)
return sell[k]
ตัวอย่าง Trace (prices=[7,3,5,2,3], k=2)
Day 0 (7): Buy1=-7, Sell1=0, Buy2=-7, Sell2=0
Day 1 (3): Buy1=-3, Sell1=0, Buy2=-3, Sell2=0
Day 2 (5): Buy1=-3, Sell1=2, Buy2=-1, Sell2=2
Day 3 (2): Buy1=-2, Sell1=2, Buy2=0, Sell2=2
Day 4 (3): Buy1=-2, Sell1=3, Buy2=0, Sell2=3 ← Answer
Key Insight: k ≥ n/2 → Unlimited Transactions Problem (Greedy: Sum All Positive Diffs)
