Phỏng vấn

Chuỗi bài toán Mua bán cổ phiếu (Best Time to Buy and Sell Stock): Khung Máy trạng thái QHĐ

Trong các buổi phỏng vấn thuật toán, đề bài Mua bán cổ phiếu (Best Time to Buy and Sell Stock) hiếm khi dừng lại ở câu hỏi cơ bản chỉ mua và bán đúng một lần. Người phỏng vấn thường bắt đầu từ phiên bản đơn giản nhất rồi liên tục thêm ràng buộc mới ngay trong cùng một buổi: cho phép mua bán không giới hạn số lần, áp đặt một ngày nghỉ bắt buộc (Cooldown) sau mỗi lần bán, thu phí giao dịch, hoặc giới hạn tối đa $k$ giao dịch. Thay vì học thuộc lòng từng mẹo rời rạc cho mỗi bài, bài viết này xây dựng một mô hình **máy trạng thái quy hoạch động (State Machine DP)** thống nhất giúp bạn giải quyết toàn bộ họ bài toán cổ phiếu trong thời gian tuyến tính $O(n)$ và không gian $O(1)$.

Ý chính
  • Phiên bản 1 giao dịch (Stock I): Lợi nhuận cao nhất khi bán ở ngày \(i\) đạt được nếu ta đã mua ở mức giá thấp nhất trong đoạn \([0..i-1]\). Chỉ cần duy trì biến đáy min_price và cập nhật best = max(best, price - min_price) trong một lượt duyệt \(O(n)\).
  • Phiên bản không giới hạn giao dịch (Stock II): Mọi đợt tăng giá kéo dài qua nhiều ngày \(p[a] \to p[b] \to p[c]\) đều có tổng độ chênh \((p[c] - p[a]) = (p[b] - p[a]) + (p[c] - p[b])\). Vì vậy chỉ cần cộng dồn mọi bước tăng dương giữa hai ngày liên tiếp: \(\sum \max(0, p[i] - p[i-1])\).
  • Mô hình Máy trạng thái thống nhất (State Machine DP): Tại cuối mỗi ngày \(i\), nhà đầu tư chỉ ở một trong số ít trạng thái hữu hạn: đang nắm giữ cổ phiếu (hold), vừa mới bán cổ phiếu xong (sold), hoặc đang đứng ngoài thị trường (rest). Mọi ràng buộc như ngày nghỉ (Cooldown) hay phí giao dịch (Fee) chỉ là trọng số hoặc điều kiện trên các mũi tên chuyển trạng thái.
  • Tối ưu hóa bộ nhớ \(O(1)\): Vì trạng thái của ngày thứ \(i\) chỉ phụ thuộc vào trạng thái của ngày \(i - 1\), ta chỉ cần dùng \(2\) đến \(3\) biến số nguyên thay vì cấp phát bảng quy hoạch động 2 chiều.

Cấp độ 1: Mua và bán tối đa một lần (Stock I — LeetCode 121)

Cho mảng prices gồm \(n\) số nguyên không âm, trong đó prices[i] là giá cổ phiếu vào ngày thứ \(i\). Bạn được phép chọn tối đa một ngày để mua và một ngày sau đó trong tương lai để bán. Hãy tìm lợi nhuận lớn nhất có thể đạt được (nếu không thể có lãi, trả về \(0\)).

Nếu thử mọi cặp ngày mua - bán \((j, i)\) với \(0 \le j \lt i \lt n\), thuật toán vét cạn mất \(O(n^2)\). Tuy nhiên, nếu ta cố định ngày bán là ngày \(i\), câu hỏi trở nên cực kỳ đơn giản: để lợi nhuận \(\text{prices}[i] - \text{prices}[j]\) lớn nhất, giá mua \(\text{prices}[j]\) (\(j \le i\)) phải nhỏ nhất có thể.

Vì vậy, khi duyệt price từ trái sang phải, ta chỉ cần duy trì hai đại lượng:

  1. min_p: mức giá thấp nhất từng xuất hiện tính từ ngày \(0\) đến ngày hiện tại.
  2. max_profit: lợi nhuận lớn nhất giữa các phương án bán tại từng ngày, cập nhật bởi max(max_profit, price - min_p).

Mối liên hệ với thuật toán Kadane: Nếu đặt \(d[i] = \text{prices}[i] - \text{prices}[i - 1]\) là mức thay đổi giá giữa hai ngày liên tiếp, thì lợi nhuận khi mua ở ngày \(j\) và bán ở ngày \(i\) chính là tổng đoạn con liên tiếp trên mảng hiệu số:

\[\text{prices}[i] - \text{prices}[j] = \sum_{k = j + 1}^{i} d[k]\]

Do đó, bài toán mua bán cổ phiếu 1 lần hoàn toàn tương đương với bài toán tìm đoạn con có tổng lớn nhất bằng thuật toán Kadane trên mảng hiệu số ngày (tương tự cách biến đổi của mảng cộng dồn).

Chuỗi bài toán Mua bán cổ phiếu: prices = [7, 1, 5, 3, 6, 4] Trái: 1 giao dịch (Mua đáy 1, Bán đỉnh 6 -> Lãi 5) — Phải: Máy trạng thái QHĐ tổng quát Theo dõi đáy min_price và lãi tối đa max_profit 7 Mua: 1 5 3 Bán: 6 (+5) 4 Ngày: 0 1 2 3 4 5 1 lần: lãi 5 | Nhiều lần: (5-1) + (6-3) = 7 Máy trạng thái QHĐ (Cooldown / Phí) hold[i] = max(hold[i-1], rest[i-1] - price[i]) sold[i] = hold[i-1] + price[i] (Vừa bán xong ở ngày i -> vào Cooldown) rest[i] = max(rest[i-1], sold[i-1]) (Đứng ngoài hoặc vừa hết 1 ngày nghỉ)
Mua bán cổ phiếu: [7, 1, 5, 3, 6, 4] So sánh 1 giao dịch, nhiều giao dịch và Cooldown 1. Một giao dịch & Không giới hạn giao dịch • Mua 1 lần: giữ đáy min_price = 1 (ngày 1), bán tại giá 6 (ngày 4) -> Lãi lớn nhất = 5. • Mua bán nhiều lần: gom mọi nhịp tăng dương (5 - 1) + (6 - 3) = 4 + 3 = 7 2. Máy 3 trạng thái (Có ngày nghỉ Cooldown) hold = max(hold, rest - price) sold = hold + price rest = max(rest, sold_trước)
Hình 1: Đồ thị giá prices = [7, 1, 5, 3, 6, 4] minh họa điểm mua tại đáy 1 (ngày \(1\)) và bán tại đỉnh 6 (ngày \(4\)) thu lợi nhuận bằng \(5\) cho trường hợp \(1\) giao dịch, đặt cạnh sơ đồ máy \(3\) trạng thái (hold, sold, rest) cho bài toán có ngày nghỉ Cooldown.

Cấp độ 2: Mua bán không giới hạn số lần (Stock II — LeetCode 122)

Sang câu hỏi tiếp theo, người phỏng vấn cho phép bạn thực hiện bao nhiêu giao dịch tùy ý (mua rồi bán nhiều lần), miễn là tại mỗi thời điểm chỉ được giữ tối đa \(1\) cổ phiếu (phải bán cổ phiếu đang giữ trước khi mua lại).

Giả sử giá cổ phiếu tăng liên tiếp trong ba ngày: ngày 1 giá \(1\), ngày 2 giá \(3\), ngày 3 giá \(6\). Mua ở ngày 1 và bán ở ngày 3 thu lời \(6 - 1 = 5\). Nếu ta mua ở ngày 1, bán ở ngày 2 (lời \(3 - 1 = 2\)), rồi mua lại ngay ở ngày 2 và bán ở ngày 3 (lời \(6 - 3 = 3\)), tổng lợi nhuận vẫn đúng bằng \(2 + 3 = 5\)!

Tính chất cộng tính này cho phép ta chẻ mọi con sóng tăng giá dài hạn thành các nhịp tăng giá giữa hai ngày kề nhau: cứ hễ ngày hôm nay giá cao hơn ngày hôm qua (\(\text{prices}[i] \gt \text{prices}[i - 1]\)), ta cộng ngay phần chênh lệch dương đó vào tổng lợi nhuận:

\[\text{Profit}_{\text{II}} = \sum_{i = 1}^{n - 1} \max\big(0,\; \text{prices}[i] - \text{prices}[i - 1]\big)\]

Cấp độ 3: Máy trạng thái Quy hoạch động cho Cooldown và Phí giao dịch

Khi người phỏng vấn thêm ràng buộc sau khi bán cổ phiếu, bạn không được mua lại vào ngày kế tiếp (Cooldown 1 ngày — LeetCode 309) hoặc mỗi lần bán phải trả một khoản phí giao dịch cố định fee (LeetCode 714), mẹo cộng dồn chênh lệch dương ở Cấp độ 2 không còn áp dụng trực tiếp được nữa vì một giao dịch nhỏ lẻ hôm nay có thể khóa mất cơ hội mua ở đáy lớn vào ngày mai.

Đây là lúc mô hình quy hoạch động 1 chiều dưới dạng Máy trạng thái (State Machine) phát huy sức mạnh tuyệt đối. Với bài toán có ngày nghỉ Cooldown, tại cuối mỗi ngày \(i\), ta định nghĩa lợi nhuận tối đa ứng với \(3\) trạng thái độc lập:

  1. hold[i] (Đang giữ cổ phiếu): Cuối ngày \(i\) trong tay bạn đang có \(1\) cổ phiếu. Trạng thái này đạt được theo hai cách:

    • Giữ nguyên cổ phiếu đã có từ ngày \(i - 1\): lợi nhuận giữ nguyên là hold[i - 1].
    • Hôm nay mới đặt lệnh mua ở giá prices[i]: vì có luật Cooldown, ngày \(i - 1\) bạn không được vừa mới bán xong mà bắt buộc phải đang ở trạng thái nghỉ rest[i - 1], nên lợi nhuận sau khi trừ tiền mua là rest[i - 1] - prices[i]. \[\text{hold}[i] = \max\big(\text{hold}[i - 1],\; \text{rest}[i - 1] - \text{prices}[i]\big)\]
  2. sold[i] (Vừa bán cổ phiếu ngay trong ngày \(i\)): Hôm nay bạn bán cổ phiếu đang giữ từ ngày \(i - 1\) để thu tiền mặt prices[i] về: \[\text{sold}[i] = \text{hold}[i - 1] + \text{prices}[i]\]

  3. rest[i] (Đang đứng ngoài và sẵn sàng mua vào ngày mai): Cuối ngày \(i\) bạn không giữ cổ phiếu và cũng không bán gì trong ngày \(i\). Trạng thái này đến từ hai nguồn:

    • Tiếp tục đứng ngoài như ngày \(i - 1\): rest[i - 1].
    • Vừa kết thúc ngày nghỉ bắt buộc sau khi đã bán cổ phiếu ở ngày \(i - 1\): sold[i - 1]. \[\text{rest}[i] = \max\big(\text{rest}[i - 1],\; \text{sold}[i - 1]\big)\]

Khởi tạo tại ngày \(0\): hold = -prices[0], sold = 0, rest = 0. Sau khi duyệt hết \(n\) ngày, đáp án lớn nhất không nằm ở hold (vì còn kẹt tiền trong cổ phiếu chưa bán) mà là \(\max(\text{sold}, \text{rest})\).

Biến thể bài toán Số trạng thái cần nhớ Công thức chuyển trạng thái mỗi ngày p = prices[i] Thời gian & Bộ nhớ phụ
Stock I (Tối đa 1 lần) \(2\) biến (min_p, ans) min_p = min(min_p, p); ans = max(ans, p - min_p) \(O(n)\) thời gian, \(O(1)\) bộ nhớ
Stock II (Vô hạn lần) \(2\) trạng thái (hold, cash) hold = max(hold, cash - p); cash = max(cash, hold + p) \(O(n)\) thời gian, \(O(1)\) bộ nhớ
Stock + Phí (fee) \(2\) trạng thái (hold, cash) hold = max(hold, cash - p); cash = max(cash, hold + p - fee) \(O(n)\) thời gian, \(O(1)\) bộ nhớ
Stock + Cooldown 1 ngày \(3\) trạng thái (hold, sold, rest) hold = max(hold, rest - p); sold = prev_hold + p; rest = max(rest, prev_sold) \(O(n)\) thời gian, \(O(1)\) bộ nhớ
Stock III & IV (Tối đa \(k\) lần) \(2k\) trạng thái (hold[1..k], cash[1..k]) Với mỗi giao dịch thứ \(j \in [1..k]\):
hold[j] = max(hold[j], cash[j-1] - p)
cash[j] = max(cash[j], hold[j] + p)
\(O(n \cdot k)\) thời gian, \(O(k)\) bộ nhớ

Ví dụ chạy tay từng bước với Máy trạng thái Cooldown

Ta chạy tay thuật toán máy 3 trạng thái trên mảng prices = [1, 2, 3, 0, 2] (\(n = 5\)), đồng thời theo dõi luôn kết quả của Stock I (1 lần) và Stock II (nhiều lần không Cooldown) để thấy rõ sự khác biệt.

Ngày \(i\) Giá p Stock I (min_p, best1) Stock II (best2 cộng dồn) Máy trạng thái Cooldown: hold sold rest Giải thích trạng thái Cooldown tối ưu
0 1 min_p = 1, best1 = 0 0 -1 0 0 Mua cổ phiếu giá 1 (hold = -1) hoặc đứng ngoài (rest = 0).
1 2 min_p = 1, best1 = 1 \(0 + (2 - 1) = \mathbf{1}\) -1 1 0 Nếu bán hôm nay: sold = -1 + 2 = 1. Nếu giữ: hold = -1.
2 3 min_p = 1, best1 = 2 \(1 + (3 - 2) = \mathbf{2}\) -1 2 1 Nếu bán hôm nay: sold = -1 + 3 = 2. Nếu nghỉ sau khi bán ở ngày 1: rest = 1.
3 0 min_p = 0, best1 = 2 \(2 + 0 = \mathbf{2}\) 1 -1 2 Nhờ đã bán ở ngày 1 và nghỉ ở ngày 2 (rest = 1), hôm nay mua lại giá 0 được hold = 1 - 0 = 1!
4 2 min_p = 0, best1 = 2 \(2 + (2 - 0) = \mathbf{4}\) 1 3 2 Bán cổ phiếu đang giữ (hold = 1) ở giá 2 thu về sold = 1 + 2 = 3.

Kết thúc ngày \(4\):

  • Stock I (1 giao dịch): Mua ở giá 1 (ngày 0), bán ở giá 3 (ngày 2) \(\implies\) lợi nhuận bằng 2.
  • Stock II (Nhiều giao dịch không nghỉ): Mua ngày 0 bán ngày 2 (lãi 2), mua lại ngay ngày 3 (giá 0) bán ngày 4 (giá 2, lãi 2) \(\implies\) tổng lợi nhuận bằng 4.
  • Stock có Cooldown: Nếu bán ở ngày 2 thì ngày 3 bị khóa Cooldown không mua được đáy giá 0. Máy trạng thái tự động tìm ra phương án bán sớm ở ngày 1 (giá 2, lãi 1), nghỉ ngày 2, mua đáy ngày 3 (giá 0) và bán ngày 4 (giá 2, lãi thêm 2) \(\implies\) tổng lợi nhuận bằng 3.

Cài đặt bằng C++17, Python và Java 21

Chương trình dưới đây cài đặt đồng thời cả ba bài toán (Stock I, Stock II và Stock với Cooldown) chỉ trong một lượt duyệt mảng duy nhất với thời gian \(O(n)\) và bộ nhớ phụ \(O(1)\), in ra ba kết quả cách nhau bởi khoảng trắng.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

long long stock_one_tx(const vector<long long>& p) {
    long long min_price = p[0], best = 0;
    for (long long x : p) {
        best = max(best, x - min_price);
        min_price = min(min_price, x);
    }
    return best;
}

long long stock_unlimited_tx(const vector<long long>& p) {
    long long profit = 0;
    for (size_t i = 1; i < p.size(); i++) {
        if (p[i] > p[i - 1]) profit += p[i] - p[i - 1];
    }
    return profit;
}

long long stock_with_cooldown(const vector<long long>& p) {
    long long hold = -p[0], sold = 0, rest = 0;
    for (size_t i = 1; i < p.size(); i++) {
        long long prev_hold = hold;
        long long prev_sold = sold;
        long long prev_rest = rest;
        hold = max(prev_hold, prev_rest - p[i]);
        sold = prev_hold + p[i];
        rest = max(prev_rest, prev_sold);
    }
    return max(sold, rest);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) {
        vector<long long> sample = {1, 2, 3, 0, 2};
        cout << stock_one_tx(sample) << " "
             << stock_unlimited_tx(sample) << " "
             << stock_with_cooldown(sample) << "\n";
        return 0;
    }
    vector<long long> p(n);
    for (int i = 0; i < n; i++) cin >> p[i];
    cout << stock_one_tx(p) << " "
         << stock_unlimited_tx(p) << " "
         << stock_with_cooldown(p) << "\n";
    return 0;
}

Các lỗi sai thường gặp và cách tự kiểm chứng

  1. Ghi đè biến trạng thái của ngày \(i - 1\) trước khi tính xong các trạng thái còn lại của ngày \(i\): Trong vòng lặp cập nhật hold, sold, rest, cả ba công thức đều phải dùng giá trị của ngày hôm trước (prev_hold, prev_sold, prev_rest). Nếu bạn gán sold = hold + p rồi ngay dòng dưới viết rest = max(rest, sold), thì rest đã vô tình lấy sold mới của ngày hôm nay, nên ngày mai hold = max(hold, rest - p) được phép mua lại ngay sau ngày bán, phá luật Cooldown: với prices = [6, 8, 1, 9], cách ghi đè này trả về 10 thay vì đáp án đúng 8. (Riêng việc sold dùng hold mới không làm sai kết quả, vì mua và bán trong cùng một ngày chỉ lãi \(0\).) Hãy luôn sao lưu prev_hold = hold, prev_sold = sold, prev_rest = rest ở đầu mỗi bước lặp.
  2. Khởi tạo hold = 0 thay vì -prices[0] (hoặc \(-\infty\)): Ở ngày đầu tiên, để có cổ phiếu trong tay (hold), bạn bắt buộc phải bỏ tiền túi ra mua với giá prices[0], nên tài khoản tiền mặt đang âm -prices[0]. Nếu khởi tạo hold = 0, chương trình sẽ hiểu nhầm là bạn được tặng không một cổ phiếu miễn phí từ đầu!
  3. Cách tự kiểm chứng tại nhà: Bạn có thể viết một hàm đệ quy quay lui có nhớ (memoization) đơn giản dfs(day, state) cho mảng ngắn \(n \le 12\) để thử cả 3 quyết định (mua, bán, đứng im) ở mỗi ngày và so sánh kết quả với hàm máy trạng thái \(O(1)\) bộ nhớ. Hãy đặc biệt thử các mảng giảm dần hoàn toàn như [7, 6, 4, 3, 1] (mọi biến thể đều phải trả về đúng 0, không được trả về số âm) và mảng dao động răng cưa [1, 5, 2, 8, 1, 9].

Luyện ngay trên Big-O Coding

Để áp dụng ngay mô hình máy trạng thái quy hoạch động vừa học vào các bài toán giao dịch tài chính thực tế, bạn hãy thử sức với chuỗi bài tập mua bán cổ phiếu trong lộ trình Coding Interview 150:

Trong bài toán Mua bán cổ phiếu có phí giao dịch (Transaction Fee — LeetCode 714), nên trừ phí lúc mua hay lúc bán?

Trừ phí fee ở lúc mua hay lúc bán đều cho cùng một kết quả cuối cùng vì một giao dịch hoàn chỉnh luôn gồm đủ một cặp Mua + Bán, và đáp án cuối cùng luôn kết thúc ở trạng thái không giữ cổ phiếu (cash). Tuy nhiên, trong C++ hoặc Java, nếu bạn khởi tạo hold = INT_MIN (không chia đôi) rồi trừ fee lúc bán (hold + price - fee), phép tính sẽ tràn số âm (underflow) khi price < fee. Vì vậy, khởi tạo hold = -prices[0] và trừ fee ở bước bán (cash = max(cash, hold + price - fee)) là cách viết an toàn nhất.

Khi giới hạn tối đa \(k\) giao dịch (LeetCode 188) mà \(k\) rất lớn (\(k \ge n / 2\)), ta có thể tối ưu như thế nào?

Một giao dịch sinh lời thực sự cần ít nhất \(2\) ngày (1 ngày mua giá thấp và 1 ngày bán giá cao). Trong khoảng thời gian \(n\) ngày, số đợt sóng tăng giá độc lập tối đa không thể vượt quá \(\lfloor n / 2 \rfloor\). Do đó, nếu đề bài cho \(k \ge n / 2\), ràng buộc số lần giao dịch trở nên dư thừa và bài toán suy biến hoàn toàn về Stock II (mua bán không giới hạn số lần), giải ngay trong \(O(n)\) thời gian và \(O(1)\) bộ nhớ thay vì \(O(n \cdot k)\).

Nếu người phỏng vấn yêu cầu in ra cụ thể ngày mua và ngày bán của phương án tối ưu thì làm sao?

Với Stock I (1 giao dịch), mỗi khi cập nhật min_p = prices[i], bạn lưu lại chỉ số candidate_buy = i; mỗi khi prices[i] - min_p > max_profit, bạn chốt best_buy = candidate_buy và best_sell = i. Với máy trạng thái quy hoạch động (Cooldown, Fee, \(k\) giao dịch), bạn cần giữ lại mảng trạng thái 2 chiều dp[n][state] (bộ nhớ \(O(n)\)) kèm mảng truy vết parent_state[n][state] ghi lại xem trạng thái ở ngày \(i\) được chuyển tới từ trạng thái nào ở ngày \(i - 1\), sau đó lần ngược từ ngày \(n - 1\) về ngày \(0\) để liệt kê các ngày xảy ra chuyển tiếp rest -> hold (ngày mua) và hold -> sold (ngày bán).

Muốn học bài bản cùng giảng viên?

Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483