Chương trình tìm lợi nhuận tối đa sau k lần Mua/Bán cổ phiếu trong Python

Cho danh sách prices giá cổ phiếu theo thứ tự thời gian và số k. Tìm lợi nhuận tối đa từ tối đa k lần mua/bán (phải mua trước bán, bán trước mua lại).

Ví dụ: prices=[7,3,5,2,3], k=2 → output 3 (mua 3 bán 5, mua 2 bán 3).

Thuật toán DP đệ quy + Memoization:

• Trạng thái: dp(i, k, bought) = lợi nhuận max từ ngày i với k giao dịch còn lại, bought = có đang nắm cổ phiếu không
• Base case: i == n hoặc k == 0 → 0
• Nếu bought: max(bán hôm nay: dp(i+1, k-1, False) + prices[i], giữ: dp(i+1, k, True))
• Nếu not bought: max(mua hôm nay: dp(i+1, k, True) - prices[i], không mua: dp(i+1, k, False))

Triển khai

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))

Đầu vào

[7, 3, 5, 2, 3], 2

Đầu ra

3

Lưu ý: Code đệ quy không có memoization → O(2^n) rất chậm. Cần thêm @lru_cache(None) hoặc DP bottom-up. DP bottom-up tối ưu: dp[t][i][0/1] = max profit dùng ≤t transactions đến ngày i, không nắm/nắm stock. Phức tạp O(k×n).

Tối ưu O(k×n) bottom-up:

def maxProfit(k, prices):
    n = len(prices)
    if k >= n // 2:  # Unlimited transactions
        return sum(max(0, prices[i+1]-prices[i]) for i in range(n-1))
    dp = [[0]*n for _ in range(k+1)]
    for t in range(1, k+1):
        max_diff = -prices[0]
        for i in range(1, n):
            dp[t][i] = max(dp[t][i-1], prices[i] + max_diff)
            max_diff = max(max_diff, dp[t-1][i] - prices[i])
    return dp[k][n-1]