- 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_pricevà cập nhậtbest = 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:
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.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ởimax(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).
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:
-
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)\]
- Giữ nguyên cổ phiếu đã có từ ngày \(i - 1\): lợi nhuận giữ nguyên là
-
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ặtprices[i]về: \[\text{sold}[i] = \text{hold}[i - 1] + \text{prices}[i]\] -
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)\]
- Tiếp tục đứng ngoài như ngày \(i - 1\):
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ằng2. - 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ãi2) \(\implies\) tổng lợi nhuận bằng4. - 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ãi1), nghỉ ngày 2, mua đáy ngày 3 (giá0) và bán ngày 4 (giá2, lãi thêm2) \(\implies\) tổng lợi nhuận bằng3.
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;
}
import sys
def stock_one_tx(p: list[int]) -> int:
min_price = p[0]
best = 0
for x in p:
if x - min_price > best:
best = x - min_price
if x < min_price:
min_price = x
return best
def stock_unlimited_tx(p: list[int]) -> int:
return sum(max(0, p[i] - p[i - 1]) for i in range(1, len(p)))
def stock_with_cooldown(p: list[int]) -> int:
hold, sold, rest = -p[0], 0, 0
for x in p[1:]:
hold, sold, rest = max(hold, rest - x), hold + x, max(rest, sold)
return max(sold, rest)
def main():
tokens = sys.stdin.read().split()
if not tokens:
s = [1, 2, 3, 0, 2]
print(f"{stock_one_tx(s)} {stock_unlimited_tx(s)} {stock_with_cooldown(s)}")
return
n = int(tokens[0])
p = [int(x) for x in tokens[1:1 + n]]
print(f"{stock_one_tx(p)} {stock_unlimited_tx(p)} {stock_with_cooldown(p)}")
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
public static long stockOneTx(long[] p) {
long minPrice = p[0], best = 0;
for (long x : p) {
best = Math.max(best, x - minPrice);
minPrice = Math.min(minPrice, x);
}
return best;
}
public static long stockUnlimitedTx(long[] p) {
long profit = 0;
for (int i = 1; i < p.length; i++) {
if (p[i] > p[i - 1]) profit += p[i] - p[i - 1];
}
return profit;
}
public static long stockWithCooldown(long[] p) {
long hold = -p[0], sold = 0, rest = 0;
for (int i = 1; i < p.length; i++) {
long prevHold = hold, prevSold = sold, prevRest = rest;
hold = Math.max(prevHold, prevRest - p[i]);
sold = prevHold + p[i];
rest = Math.max(prevRest, prevSold);
}
return Math.max(sold, rest);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) {
long[] s = {1, 2, 3, 0, 2};
System.out.println(stockOneTx(s) + " " + stockUnlimitedTx(s) + " " + stockWithCooldown(s));
return;
}
int n = sc.nextInt();
long[] p = new long[n];
for (int i = 0; i < n; i++) p[i] = sc.nextLong();
System.out.println(stockOneTx(p) + " " + stockUnlimitedTx(p) + " " + stockWithCooldown(p));
}
}
Các lỗi sai thường gặp và cách tự kiểm chứng
- 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ánsold = hold + prồi ngay dòng dưới viếtrest = max(rest, sold), thìrestđã vô tình lấysoldmới của ngày hôm nay, nên ngày maihold = max(hold, rest - p)được phép mua lại ngay sau ngày bán, phá luật Cooldown: vớiprices = [6, 8, 1, 9], cách ghi đè này trả về10thay vì đáp án đúng8. (Riêng việcsolddùngholdmớ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ưuprev_hold = hold,prev_sold = sold,prev_rest = restở đầu mỗi bước lặp. - Khởi tạo
hold = 0thay 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ạohold = 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! - 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ề đúng0, 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).
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.


