代码随想录算法训练营 Day 35
Published:
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组
第5步随着输入不同而变化，因此在此省去
Q1. LeetCode 121
前四步：
- 使用二维的dp数组，dp[i][0]表示第i天不持有股票的情况最多有多少钱，dp[i][1]表示第i天持有股票的情况最多有多少钱
- 递推公式：1. 持有股票的情况分两种：1）在前面就已经有股票了，这个时候钱就是前一天的情况一样；2）在这一天买进了股票，这个时候身上的钱就是股价的负数（将钱已经买成股票了），因此 $dp[i][1] = max(dp[i-1][1], -prices[i])$。2. 同理，不持有股票也有两种情况：1）到现在还没有买进股票，这个时候钱和前一天一样；2）这一天将股票卖出，这个时候身上的钱就是卖出价格减去买入成本，因此 $dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])$
- 初始化：整体初始化为0，其中$dp[i][1]=-prices[0]$, $dp[i][0]=0$
- 遍历顺序：从前向后遍历
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 贪心法
# res = float('-inf')
# lowest_price = prices[0]
# for i in range(1, len(prices)):
# curr = prices[i]
# if curr < lowest_price:
# lowest_price = curr
# else:
# res = max(res, curr - lowest_price)
# return res if res != float('-inf') else 0
# 动态规划
n = len(prices)
dp = [[0] * 2 for _ in range(n)]
dp[0][1] = -prices[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], -prices[i])
return dp[-1][0]
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n \times 2$)
Q2. LeetCode 122
思路和Q1类似，依然采用二维dp数组，但是因为可能存在多次买卖交易，所以某一天持有股票是最多的钱情况有所不同：1）之前就持有股票，那么当前还是和前一天情况相同；2）如果在当天买进了股票，应该是前一天没有持有股票情况下最多钱（考虑之前交易的收益）减去当天股票价格
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# if len(prices) == 1:
# return 0
# n = len(prices)
# diff = [0] * (n - 1)
# for i in range(n - 1):
# diff[i] = prices[i + 1] - prices[i]
# res = 0
# for d in diff:
# if d >= 0:
# res += d
# return res
n = len(prices)
dp = [[0] * 2 for _ in range(n)]
dp[0][1] = -prices[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 dp[-1][0]
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n \times 2$)
Q3. LeetCode 123
题目描述中至多只能有两次交易，并且最后不能让手里有股票，因为买股票要花钱，所以设置一个二维dp数组，dp[i][0]代表从来手里都没有股票，dp[i][1]代表手里第一次有股票，dp[i][2]代表之前手里的股票卖掉了，dp[i][3]代表重新买了一次股票，dp[i][4]代表股票又被卖掉了
注意：每种情况都有两种可能性：1）和前一天的状态一样（即之前就已经有过操作）；2）恰好在当天进行了操作
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
# 0: 没有股票；1: 有股票；2：再次没有股票；3. 再次有股票；4. 第三次没有股票（最多只能有两次交易，不需要再考虑买入情况）
dp = [[0] * 5 for _ in range(n)]
dp[0][1] = -prices[0]
dp[0][3] = -prices[0]
for i in range(1, n):
dp[i][0] = dp[i - 1][0]
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])
return dp[-1][4]
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n \times 5$)