Dynamic Programming (2)
Thứ Hai,
28/10/2024
admin
Best time to buy and sell stock là 1 series rất hay để học cách tư duy theo kiểu Dynamic Programming. Với bài toán ban đầu chỉ đơn giản là: cho một prices list ứng với giá stock trong n ngày, chọn một ngày Buy và một ngày Sell sao cho maximize được profit, sau đó bài toán được biến thể với rất nhiều constraints khác nhau. Hãy cùng xem Dynamic Programming linh hoạt như nào trong việc hoá giải các constraints đó.
1 Buy and Sell Stock with 1 transaction
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
You are given an array prices where prices[i] is the price of a given stock on the i<sup>th</sup> day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.
Brute force
- Dùng 1 biến i để duyệt lần lượt từng ngày Buy
- Với mỗi ngày Buy, dùng 1 biến j để duyệt từng ngày Sell. Vì ngày Sell phải sau ngày Buy nên j > i
- Update max_profit sau mỗi lần duyệt như vậy
Dễ thấy độ phức tạp của giải thuật 2 vòng loop này là O(n^2)
Dynamic Programming
Gọi T[i] là profit tối ưu (max_profit) tính tới ngày thứ i. Khi đó T[i] có thể rơi vào 1 trong 2 cases:
- T[i-1]: không Sell tại ngày i
- price[i] – lowest: Sell tại ngày i và Buy tại mức giá thấp nhất (lowest) trước đó
Do đó:
- lowest = lowest price upto i-1 day
- T[i] = max(T[i-1], price[i] – lowest)
Độ phức tạp lúc này giảm còn O(n)
2 Buy and sell with no limit transaction
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
You are given an array prices where prices[i] is the price of a given stock on the i<sup>th</sup>; day.
Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e., max profit = 0.
Trick: nhận thấy max profit trong trường hợp này có thể đạt được bằng cách ‘chốt lời’ liên tục, nghĩa là cứ thấy prices[j] > prices[i] với j>i là ‘chốt’ nên chỉ cần duyệt 1 lần, lần lượt từ đầu tới cuối prices list
Dynamic Programming (1)
Tuy nhiên việc nhận ra trick không dễ, với bài này ta có thể nghĩ ngay tới giải pháp Dynamic Programming 1 cách ‘tự nhiên’ hơn như sau:
Gọi T[i] là max profit tính tới ngày thứ i, khi đó T[i] có thể rơi vào 1 trong 2 cases sau:
- T[i-1]: không làm gì vào ngày thứ i
- max(prices[i] – prices[j] + T[j-1] với j = 0 to i-1): Sell tại ngày i và Buy tại ngày j nào đó trước i)
Do đó:
T[i] = max(T[i-1], prices[i] – prices[j] + T[j-1]) for j from 0 to i
Độ phức tạp của giải thuật 2 vòng loop này là O(n^2)
Dynamic Programming (2)
Nhận thấy trong biểu thức prices[i] – prices[j] + T[j-1] = prices[i] – (prices[j] – T[j-1]) thì prices[j] – T[j-1] bị tính lặp lại nhiều. Ta có thể giảm xuống 1 vòng loop như sau:
Độ phức tạp của giải thuật lúc này giảm xuống còn O(n)
3 Buy and sell with k limit transaction
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
You are given an integer array prices where prices[i] is the price of a given stock on the i<sup>th</sup> day, and an integer k.
Find the maximum profit you can achieve. You may complete at most k transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: k = 2, prices = [2,4,1] Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: k = 2, prices = [3,2,6,5,0,3] Output: 7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Dynamic Programming (1)
Bài này giống bài 5.2 ở trên nhưng có contrains thêm yếu tố k transactions nên ta sử dụng thêm 1 biến k nữa để modelling bài toán.
Gọi T[k][i] là maximum profit tại transaction k và tính tới ngày thứ i. Khi đó T[k][i] có thể rơi vào 1 trong 2 trường hợp:
- T[k][i-1]: không hành động gì tại ngày thứ i
- max(prices[i]-prices[m]+T[k-1][m-1] for m from 0 to i-1): Sell tại ngày i và bán tại ngày m nào đó trước i
Do đó:
T[k][i] = max(T[k][i-1], prices[i]-prices[m]+T[k-1][m-1] for m from 0 to i-1)
Độ phức tạp của giải thuật 3 vòng loop này là O(n^3)
Dynamic Programming (2)
Nhận thấy trong biểu thức prices[i] – prices[m] + T[j-1][m-1] = prices[i] – (prices[m] – T[j-1][m-1) thì prices[m] – T[j-1][m-1] bị tính lặp lại nhiều. Ta có thể giảm xuống 2 vòng loop như sau:
Độ phức tạp của giải thuật giảm xuống còn O(n^2)
4 Buy and sell with cool down
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
You are given an array prices where prices[i] is the price of a given stock on the i<sup>th </sup>day.
Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:
- After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,2,3,0,2] Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]
Example 2:
Input: prices = [1] Output: 0
Dynamic Programming (1)
Bài này giống bài 5.2 tuy nhiên có thêm điều kiện là phải nghỉ thêm 1 ngày cool down trước khi được Buy tiếp
Gọi T[i] là maximum profit tới ngày thứ i. Khi đó T[i] có thể rơi vào 1 trong 2 cases:
- T[i-1]: không hành động gì vào ngày i
- max(prices[i]-prices[j]+T[j-2] for j from 0 to i-1): Sell tại ngày i và Buy tại ngày j nào đó trước i
Do đó:
T[i] = max(T[i-1], prices[i] – prices[j] + T[j-2] for j from 0 to i-1)
Độ phức tạp của giải thuật này là O(n^2)
Dynamic Programming (2)
Tương tự, nhận thấy trong biểu thức prices[i] – prices[j] + T[j-2] = prices[i] – (prices[j] – T[j-2]) thì prices[j] – T[j-2] bị tính lặp lại nhiều. Ta có thể giảm xuống 1 vòng loop như sau:
Độ phức tạp của giải thuật được giảm xuống còn O(n)
5 Buy and sell with fee
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
You are given an array prices where prices[i] is the price of a given stock on the i<sup>th </sup>day, and an integer fee representing a transaction fee.
Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,3,2,8,4,9], fee = 2 Output: 8 Explanation: The maximum profit can be achieved by: - Buying at prices[0] = 1 - Selling at prices[3] = 8 - Buying at prices[4] = 4 - Selling at prices[5] = 9 The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3 Output: 6
Dynamic Programming (1)
Bài này giống bài 5.2 tuy nhiên có thêm điều kiện là ta bị mất một khoản fee sau mỗi lần Sell
Gọi T[i] là maximum profit tới ngày thứ i. Khi đó T[i] có thể rơi vào 1 trong 2 cases:
- T[i-1]: không hành động gì vào ngày i
- max(prices[i] – prices[j] + T[j-1] – fee for j from 0 to i-1): Sell tại ngày i và Buy tại ngày j nào đó trước i
Do đó:
T[i] = max(T[i-1], prices[i] – prices[j] + T[j-1] – fee)
Độ phức tạp của giải thuật 2 vòng loop này là O(n^2)
Dynamic Programming (2)
Tương tự, nhận thấy trong biểu thức prices[i] – prices[j] + T[j-1] – fee = prices[i] – fee – (prices[j] – T[j-1]) thì prices[j] – T[j-1] bị tính lặp lại nhiều. Ta có thể giảm xuống 1 vòng loop như sau:
Độ phức tạp giảm xuống còn O(n)
