121. 买卖股票的最佳时机
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
思路
代码
class Solution:
def maxProfit(self, prices: List[int]) -> int:
## 动态规划
dp_0, dp_1 = 0, float('-inf')
for price in prices:
dp_0 = max(dp_0, dp_1+price)
dp_1 = max(dp_1, -price)
return dp_0
复杂度
- 时间复杂度：
- 空间复杂度：
122. 买卖股票的最佳时机 II
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
思路
代码
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp_0, dp_1 = 0, float('-inf')
for price in prices:
dp_0, dp_1 = max(dp_0, dp_1+price), max(dp_1, dp_0-price)
return dp_0
复杂度
- 时间复杂度：
- 空间复杂度：
123. 买卖股票的最佳时机 III
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
思路
代码
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n, K = len(prices), 2
dp = [ [ [0]*2 for _ in range(K+1) ] for _ in range(n) ]
for i in range(n):
for k in range(K, 0, -1):
if not i:
dp[i][k][0], dp[i][k][1] = 0, -prices[i]
continue
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
return dp[n-1][K][0]
复杂度
- 时间复杂度：
- 空间复杂度：
188. 买卖股票的最佳时机 IV
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
思路
代码
class Solution:
def maxProfitInf(self, prices: List[int]) -> int:
dp_0, dp_1 = 0, float('-inf')
for price in prices:
dp_0, dp_1 = max(dp_0, dp_1+price), max(dp_1, dp_0-price)
return dp_0
def maxProfit(self, K: int, prices: List[int]) -> int:
n = len(prices)
if K > n//2:
return self.maxProfitInf(prices)
dp = [ [ [0]*2 for _ in range(K+1) ] for _ in range(n) ]
for i in range(n):
for k in range(K, 0, -1):
if not i:
dp[i][k][0], dp[i][k][1] = 0, -prices[i]
continue
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
return dp[n-1][K][0]
复杂度
- 时间复杂度：
- 空间复杂度：