121. 买卖股票的最佳时机
- 思路
- example
- 交易一次
- 贪心，找前低
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
pre_low = prices[0]
res = 0
for i in range(1, len(prices)):
res = max(res, prices[i] - pre_low)
pre_low = min(pre_low, prices[i])
return res
- DP, 二维，加状态
- dp[i][0]: 第i天持有股票 (不一定是第i天买入） 最大利润
- dp[i][1]: 第i天不持有股票 （不一定是第i天卖出） 最大利润
- Goal: max(dp[n-1])
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0 for _ in range(2)] for _ in range(n)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], -prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
return max(dp[n-1])
- 可空间优化
122. 买卖股票的最佳时机 II
- 思路
- example
- 交易次数不限
- 贪心，累加正收益
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
for i in range(1, len(prices)):
res += max(prices[i] - prices[i-1], 0)
return res
- DP, 二维，带状态
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0 for _ in range(2)] for _ in range(n)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
return max(dp[n-1])
123. 买卖股票的最佳时机 III
- 思路
- example
- 最多两笔交易
- DP, 三维 (j,k可合并成一维）
- dp[i][j][k]: 第i天，第j次交易 (j=1,2)，状态k 的最大利润
- k=0: 持有 (已买入）
- k=1: 不持有 (已卖出）
- 注意：先买后卖
- dp[i][j][k]: 第i天，第j次交易 (j=1,2)，状态k 的最大利润
j = 1, 2:
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1]-prices[i])
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0]+prices[i])
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
m = 2
dp = [[[0] * 2 for _ in range(m+1)] for _ in range(len(prices))]
dp[0][0] = [-float('inf'), 0]
dp[0][1] = [-prices[0], -float('inf')]
dp[0][2] = [-float('inf'), -float('inf')]
for i in range(1, len(prices)):
for j in range(1, m+1):
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1]-prices[i])
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0]+prices[i])
return max(dp[-1][j][1] for j in range(m+1))
# 第几次交易在第三个维度
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[[0 for _ in range(2)] for _ in range(2)] for _ in range(n)]
dp[0][0] = [-prices[0], -prices[0]]
dp[0][1] = [0, 0]
for i in range(1, n):
dp[i][0][0] = max(dp[i-1][0][0], - prices[i])
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0] + prices[i])
dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0] - prices[i])
dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][1] + prices[i])
return max(dp[n-1][1])
- 初始化可以多种解读。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
m = 2
dp = [[[0 for _ in range(2)] for _ in range(m+1)] for _ in range(n)]
dp[0][0] = [-float('inf'), 0]
dp[0][1] = [-prices[0], 0]
dp[0][2] = [-prices[0], 0]
for i in range(1, n):
for j in range(1, m+1):
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1]-prices[i])
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0]+prices[i])
return max([dp[n-1][j][1] for j in range(m+1)])
- dp[i][j][k]: 第i天，最多j次交易 (j=1,2)，状态k 的最大利润
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
k = 2
dp = [[[0 for _ in range(2)] for _ in range(k+1)] for _ in range(n)]
dp[0][0] = [-float('inf'), 0]
dp[0][1] = [-prices[0], 0]
dp[0][2] = [-prices[0], 0]
for i in range(1, n):
for j in range(1, k+1):
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1] - prices[i])
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0] + prices[i])
#return max([dp[n-1][j][1] for j in range(1, k+1)])
return dp[n-1][k][1]
188. 买卖股票的最佳时机 IV
- 思路
- example
- 最多k笔交易
- DP, 三维
- dp[i][j][l]: 第i天，j次交易 (j=1,2)，状态l 的最大利润
- l=0: 持有 (已买入）
- l=1: 不持有 (已卖出）
- 注意：先买后卖
- dp[i][j][l]: 第i天，j次交易 (j=1,2)，状态l 的最大利润
j = 1, 2, ..., k:
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1]-prices[i])
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0]+prices[i])
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
dp = [[[0] * 2 for _ in range(k+1)] for _ in range(len(prices))]
for j in range(k+1):
dp[0][j] = [-float('inf'), -float('inf')]
dp[0][0] = [-float('inf'), 0]
dp[0][1] = [-prices[0], -float('inf')]
for i in range(1, len(prices)):
for j in range(1, k+1):
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1]-prices[i])
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0]+prices[i])
return max(dp[-1][j][1] for j in range(k+1))
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
n = len(prices)
m = k
dp = [[[0 for _ in range(2)] for _ in range(m+1)] for _ in range(n)]
dp[0][0] = [-float('inf'), 0]
for j in range(1, m+1):
dp[0][j] = [-prices[0], 0]
for i in range(1, n):
for j in range(1, m+1):
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1]-prices[i])
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0]+prices[i])
return max([dp[n-1][j][1] for j in range(m+1)])
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
n = len(prices)
dp = [[[0 for _ in range(2)] for _ in range(k+1)] for _ in range(n)]
dp[0][0] = [-float('inf'), 0]
for j in range(1, k+1):
dp[0][j] = [-prices[0], 0]
for i in range(1, n):
for j in range(1, k+1):
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1]-prices[i])
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0]+prices[i])
return dp[n-1][k][1]
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
n = len(prices)
dp = [[[0 for _ in range(2)] for _ in range(k+1)] for _ in range(n)]
dp[0][0] = [0, 0]
for j in range(1, k+1):
dp[0][j] = [-prices[0], 0]
for i in range(1, n):
for j in range(1, k+1):
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1] - prices[i])
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0] + prices[i])
return dp[n-1][k][1]
