Chương trình tìm lợi nhuận tối đa mua bán cổ phiếu có phí giao dịch trong Python

Cho danh sách giá cổ phiếu prices theo thứ tự thời gian và phí giao dịch fee cho mỗi lần bán. Có thể mua/bán bất kỳ số lần nào (phải mua trước khi bán). Tìm lợi nhuận tối đa.

Ví dụ

prices = [2, 10, 4, 8], fee = 3

Mua 2, bán 10 → lãi 8 - 3 = 5

Mua 4, bán 8 → lãi 4 - 3 = 1

Tổng: 6

Thuật toán (DP với 2 trạng thái / Recursion + Memo)

Trạng thái: flag = 0 (chưa có cổ phiếu), flag = 1 (đang nắm cổ phiếu).

• recur(i, 0) = max(mua hôm nay: recur(i+1, 1) - prices[i], không mua: recur(i+1, 0))
• recur(i, 1) = max(giữ: recur(i+1, 1), bán hôm nay: recur(i+1, 0) + prices[i] - fee)

Triển khai Python (Recursion + LRU Cache)

from functools import lru_cache

class Solution:
    def solve(self, prices, fee):
        n = len(prices)
        
        @lru_cache(None)
        def recur(i, holding):
            if i == n:
                return 0
            if not holding:
                # Chưa có stock: mua hoặc nghỉ
                return max(recur(i + 1, True) - prices[i], recur(i + 1, False))
            else:
                # Đang nắm stock: bán hoặc giữ
                return max(recur(i + 1, True), recur(i + 1, False) + prices[i] - fee)
        
        return recur(0, False)

# Test
ob = Solution()
print(ob.solve([2, 10, 4, 8], 3))  # Output: 6

Phiên bản tối ưu O(1) không gian (Iterative DP)

class Solution:
    def solve(self, prices, fee):
        cash, hold = 0, -prices[0]
        for price in prices[1:]:
            cash = max(cash, hold + price - fee)
            hold = max(hold, cash - price)
        return cash

Độ phức tạp

• Đệ quy: O(n) thời gian, O(n) không gian (cache).
• Lặp: O(n) thời gian, O(1) không gian.