LeetCode 121. 买卖股票的最佳时机

尝试一：暴力解决方法

常用两个指针去遍历prices数组，dp[i]用于记录在第i天所获得的最大利润。时间复杂度是O(N^2)，超出时间限制。

Code

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""## 买入卖出的次数 <= 1## 1. dp数组定义。## dp[i] 表示第i天前所获得的最大利润## 2. dp初始化dp = [0] * (len(prices))## 3. 递推公式## 利润： diff = price[j] - price[i]## 第j天的利润大于等第i天利润，那么第j天利润 = 第i天利润 + 第j天价格 - 第i天价格## dp[j] = max(dp[j], dp[i] + prices[j] - prices[i])## 4. 遍历顺序for i in range(len(prices)):for j in range(i+1, len(prices)):if prices[j] > prices[i]:dp[j] = max(dp[j], dp[i] + prices[j] - prices[i])## 5. 打印dp数组return max(dp)

动规的思路：

1. dp数组定义：第i天时，我目前的状态有两种，一种是持有股票，另外一种是已卖出股票，因此dp数组是一个二维数组，第一维用来表示天数，第二维用来表示在这一天我目前手头的股票状态。因此，dp[i][0]表示为天数<= i 时我已购入一只股票， dp[i][1]表示为天数 <= i 时我已卖出一只股票后所获得的最大利润。

2. dp数组初始化：由于递推公式是前面推后面，因此第一个元素需要初始化。

dp[0][0] = -prices[0]: 第0天持有购买，是消费行为。为什么是-prices[0]，其实是因为现有手头现金为0，因此是0-prices[0]，结果就是-prices[0]
dp[0][1] = 0: 第0天卖出股票没有利润可言。
另外，由于dp[i][0]是针对负数求最大化，因此dp数组要用负无穷去初始化，再对特殊值进行初始化。

3. 递推公式：

dp[i][0]的情况有两种：第i天前已购买(dp[i-1][0]) / 第 i 天时才购买( 现有金额 -prices[i], 负号表示购买，是亏损了这么多钱，而本题只有买卖一次，因此现有金额是0)，为获得最大利润，我要尽可能以低的价格购入股票，因此dp[i][0] = max(dp[i-1][0], -prices[i])
相应地，dp[i][1]的情况也有两种：第i天前已卖出(dp[i-1][1]) / 第 i 天时才卖出（利润 = prices[i] - dp[i-1][0] (第i天前买入的股票才可以在第i天时卖出) ），那最大利润递推公式就是dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]) 。

Code

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""# 1. dp数组定义。由于第i天的现有股票有两种状态，一个是已买入，一个是已卖出，因此需要用一个长度为2的数组来表示这种关系
# dp[i][0], 表示第i天已买入股票的状态，这种状态描述了我在第i天前（包括第i天）购入了一只股票，值表示我购入这支股票所花的钱
# dp[i][1], 表示第i天已卖出股票的状态，这种状态描述了我在第i天前（包括第i天）卖出了一只股票，值表示我卖出这支股票所花的钱dp = [[-float('inf')] * 2 for _ in range(len(prices))]# 2. dp初始化dp[0][0] = -prices[0]dp[0][1] = 0# 3. 递推公式# dp[i][0] = max(dp[i-1][0], -prices[i])# dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])  # dp[i-1][0]+prices[i]表示第i天卖出时得到的利润# 4. 遍历顺序for i in range(len(prices)):dp[i][0] = max(dp[i-1][0], -prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])# 5. 打印dp数组if dp[-1][1] < 0:    ## 表示亏损了，那还不如不买return 0return dp[-1][1]

LeetCode 122.买卖股票的最佳时机II

思路一：贪心算法

只要有正利润就贪下来

Code

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""## 思路一：可以用贪心思路解决dp = [0] * len(prices)for i in range(1, len(prices)):margin = prices[i] - prices[i-1]if margin > 0:dp[i] = marginall_margin = sum(dp)return all_margin

思路二：动态规划

思路：

与第一题相比关键在于可以买卖多次，那第一题只能买卖一次，因此起始资金始终为0。而可以买卖多次的话，你在后续赚到钱后到起始资金就不是0了，因此这是与上道题的最大区别。

递推公式：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])

dp[i][0] = dp[i-1][0]，第i天不买入股票。
dp[i][0] = dp[i-1][1] - prices[i]，第i天买入股票，那现在就需要起始金额-购买股票金额了，起始金额为之前赚到的利润dp[i-1][1]。

dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])

dp[i][1] = dp[i-1][1]，第i天不卖出股票。
dp[i][1] = dp[i-1][0] + prices[i]，第i天卖出股票，那就需要在之前买入股票的剩余钱的基础上 + 卖出这只股票所得到的钱。

总结：dp[i][0]表示我在第i天前（包括第i天）买入股票后手头上的钱，dp[i][1]表示我在第i天前（包括第i天）卖出股票后所获得的总利润。

Code

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""## 思路二：动态规划# 1. dp数组定义dp = [ [float("-inf")]*2 for _ in range(len(prices)) ]# 2. dp初始化dp[0][0] = -prices[0]       ##  起始资金为0dp[0][1] = 0# 3. 递推公式# dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])# dp[i][1] = max(dp[i][0], dp[i-1][1] + prices[i])# 4. 遍历顺序for i in range(1, len(prices)):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])# 5. 打印dp# print(dp)return dp[-1][1]

LeetCode 123.买卖股票的最佳时机III

买卖股票的最佳时机Ⅰ是只能进行一笔交易

买卖股票的最佳时机Ⅱ是可以进行多笔交易

这道题是两笔交易，如果设置一个count来计算交易的次数，从左向右交易一次就count+1

但这种做法会陷入你前面两笔交易虽赚了，但并不是全局的最优。

思路：

为什么这道题要涉及到用多个状态来进行描述，主要影响因素在于交易次数的限制，多笔交易也可以采用多种状态来进行描述，但是由于不知道具体交易的次数，因此可以只有两个状态来进行买入和卖出的操作，并且这个买入和卖出可以继承之前已交易后的状态。
本题是两次交易，一次交易有两个状态，分别是买入和卖出，因此两次交易要通过4个状态进行描述，后面的状态依赖于前面的状态。

1. dp数组定义

dp[i][0]: 在第i天前（包括第i天）不进行股票的买入和卖出操作（这个状态可以不要）
dp[i][1]: ..., 第一次持有股票
dp[i][2]: ..., 第一次卖出股票
dp[i][3]: ..., 第二次持有股票
dp[i][4]: ..., 第二次卖出股票
可以看到1,2 是用来衡量第一笔交易的状态，3,4是用来衡量第二笔交易的状态

2. dp初始化

dp[0][0] = 0，表示在第一天不进行任何操作
dp[0][1] = -prices[0]，表示在第一天第一次买入股票
dp[0][2] = 0，表示在第一天第一次卖出股票
dp[0][3] = -prices[0]，表示在第一天第二次买入股票
dp[0][4] = 0，表示在第一天第二次卖出股票

3. 递推公式

dp[i][0] = dp[i-1][0] 表示延续之前的不操作状态
dp[i][1] = max(dp[i-1][1], -prices[i])

dp[i][1] = dp[i-1][1], 第一次操作，表示不买入股票，此时延续第i天之前买入股票后的状态；

dp[i][1] = -prices[i]，第一次操作，表示买入股票，此时起始金额为0，因此是 0 - prices[i]

dp[i][2] = max(dp[i-1][2], prices[i]+dp[i-1][1])

dp[i][2] = dp[i-1][2], 第一次操作，表示不卖出股票，此时延续第i天之前不卖出股票后的状态；

dp[i][2] = prices[i]+dp[i][1]，第一次操作，表示卖出股票，此时卖出所得prices[i] + 之前持有股票的状态dp[i-1][1] 就得到了净利润

dp[i][3] = max(dp[i-1][3], -prices[i]+dp[i-1][2])

dp[i][3] = dp[i-1][3], 第二次操作，表示买入股票，此时延续第i天之前不买入股票后的状态；

dp[i][3] = -prices[i]+dp[i-1][2]，第二次操作，表示买入股票，此时起始金额为dp[i-1][2]，因此是 dp[i-1][2] - prices[i]

dp[i][4] = max(dp[i-1][4], prices[i]+dp[i-1][3])

dp[i][4] = dp[i-1][4], 第二次操作，表示不卖出股票，此时延续第i天之前不卖出股票后的状态；

dp[i][4] = prices[i]+dp[i-1][1]，第二次操作，表示卖出股票，此时卖出所得prices[i] + 之前持有股票的状态dp[i-1][3] 就得到了两次交易后得到的净利润。

Code

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""# 1. dp数组定义：# 由于一共是两笔交易，因此买入卖出的次数是4次，因此需要通过4个状态来衡量这两笔交易# dp[i][0]: 在第i天前（包括第i天）不进行股票的买入和卖出操作  （这个状态可以不要）# dp[i][1]: ..., 第一次持有股票# dp[i][2]: ..., 第一次卖出股票# dp[i][3]: ..., 第二次持有股票# dp[i][4]: ..., 第二次卖出股票# 可以看到1,2 用来衡量第一笔交易的状态，3,4用来衡量第二笔交易的状态dp = [[float('-inf')]*5 for _ in range(len(prices))]# 2. dp数组初始化dp[0][0] = 0dp[0][1] = -prices[0]dp[0][2] = 0dp[0][3] = -prices[0]dp[0][4] = 0# 3. 递推公式# dp[i][0] = dp[i-1][0]# dp[i][1] = max(dp[i-1][1], -prices[i])# dp[i][2] = max(dp[i-1][2], prices[i]+dp[i][1])# dp[i][3] = max(dp[i-1][3], -prices[i]+dp[i-1][2])# dp[i][4] = max(dp[i-1][4], prices[i]+dp[i-1][3])# 4.遍历顺序for i in range(1, len(prices)):dp[i][0] = dp[i-1][0]        dp[i][1] = max(dp[i-1][1], -prices[i])dp[i][2] = max(dp[i-1][2], prices[i]+dp[i-1][1])dp[i][3] = max(dp[i-1][3], -prices[i]+dp[i-1][2])dp[i][4] = max(dp[i-1][4], prices[i]+dp[i-1][3])# 5. 打印dp数组# print(dp)return dp[-1][4]

另外，可以看到dp[i][0]的这个定义是不起作用的，因此实际可以只定义4个状态，没必要多定义一个不进行任何操作的状态。