動機
與309、188一起看效果更佳
Problem
You are given an array prices
where prices[i]
is the price of a given stock on the ith
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 = 2Output: 8Explanation: 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] = 9The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3Output: 6
Constraints:
1 <= prices.length <= 5 * 104
1 <= prices[i] < 5 * 104
0 <= fee < 5 * 104
Sol
現在是在賣的時候要手續費
所以原本的式子,在賣的時候要扣$$
buy[i] = sell[i-1] - prices[i] | buy[i-1]
sell[i] = buy[i-1] + prices[i] | sell[i-1]
buy[i] = sell[i-1] - prices[i] | buy[i-1]
sell[i] = buy[i-1] + prices[i] - fee | sell[i-1]
class Solution:
@functools.cache
def buy(self,i):
if i < 0:
return 0
elif i == 0:
return -self.prices[i]
else:
return max(self.sell(i-1)-self.prices[i], self.buy(i-1))
@functools.cache
def sell(self,i):
if i <= 0:
return 0
else:
return max(self.buy(i-1)+self.prices[i] - self.fee,self.sell(i-1))
def maxProfit(self, prices: List[int], fee: int) -> int:
self.fee = fee
self.prices = prices
return self.sell(len(prices)-1)