https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/
714. Best Time to Buy and Sell Stock with Transaction Fee
給你一個陣列 prices 表示股票每天的價錢,一個 fee 表示每次賣掉股票的手續費
,一天只能持有一個股票而且進行一次買或賣,求股票的最大收益。
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
思路:
1.用DP來動態的紀錄買賣狀態轉移,buy = 當天持有股票, sell = 當天不持有股票
2.當天持有股票只可能是:
一、前一天持有股票,今天不買賣
二、前一天不持有股票,今天買入
當天不持有股票只可能是:
一、前一天不持有股票,今天不買賣
二、前一天持有股票,今天賣掉
狀態轉移方程:
buy[i] = Max(buy[i-1], sell[i-1] - prices[i])
sell[i] = Max(sell[i-1], buy[i-1] + prices[i] - fee)
(賣的當下要多扣手續費)
3.最後取第 n 天的sell即可,最後一天不持有股票一定是最佳收益。
Java Code: