121. 买卖股票的最佳时机
一只股票只能买卖一次
-
输入：[7,1,5,3,6,4]
-
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
动规五部曲分析如下：
确定dp数组（dp table）以及下标的含义
dp[i][0] 表示第i天持有股票所得最多现金 ，这里可能有同学疑惑，本题中只能买卖一次，持有股票之后哪还有现金呢？
其实一开始现金是0，那么加入第i天买入股票现金就是 -prices[i]， 这是一个负数。
dp[i][1] 表示第i天不持有股票所得最多现金
注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态
很多同学把“持有”和“买入”没区分清楚。
确定递推公式
关键点：看dp[i][0]和dp[i][1]是由哪些状态推出来的
如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
- 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
- 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);（这里就保证了在股票价格最少的时候买入）
如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来
- 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
- 第i天卖出股票，那么前一天一定是持有股票的状态，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]
同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);（这里保证了在价格最高的时候卖出）
初始化dp数组
dp[i][0] 与dp[i-1][0]有关，dp[i][1]与dp[i - 1][1]，dp[i - 1][0]有关
所以要初始化dp[0][0]和dp[0][1]
i从1开始遍历
dp[0][0] :第0天持有股票所得最多现金（一定是在第0天买入了） ： -prices[0]
dp[0][1] :第1天不持有股票所得最多现金（没有买入也没有卖出） ：0
遍历顺序
后面状态依赖前面状态，所以从前往后遍历，i从1开始
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = [[0 for _ in range(2)] for _ in range(len(prices))]
#dp[i][0]表示持有股票，dp[i][1]表示不持有股票
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1,len(prices)):
#第i天持有股票:i-1天就已经买入了，或者第i天才买入
dp[i][0] = max(dp[i-1][0],-prices[i])
#第i天不持有股票:i-1天就已经不持有了，或者第i天才卖出
dp[i][1] = max(dp[i-1][1],prices[i]+dp[i-1][0])
return dp[-1][1]进一步优化：从递推公式可以看出，dp[i]只是依赖于dp[i - 1]的状态。那么我们只需要记录 当前天的dp状态和前一天的dp状态就可以了，可以使用滚动数组来节省空间
122.买卖股票的最佳时机II
这个题与上一题的区别在于：
你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
dp[i][1]和上一题是一样的，区别在于dp[i][0] ,如果只有一次买卖股票，那么我们第i天买入股票，一定是第一次买入股票，初始现金是0，那么这时的现金就是-prises[i],但是在多次买卖股票时，这时不一定是第一次买卖股票，所以现金不一定是0，那么现金如何计算呢，应该是dp[i-1][1],前一天不持有股票的最大现金（同一天可以卖入买出股票吗）
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = [[0 for _ in range(2)] for _ in range(len(prices))]
#dp[i][0]表示持有股票，dp[i][1]表示不持有股票
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1,len(prices)):
#第i天持有股票:i-1天就已经买入了，或者第i天才买入,与上一题的区别就在这里
dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i])
#第i天不持有股票:i-1天就已经不持有了，或者第i天才卖出
dp[i][1] = max(dp[i-1][1],prices[i]+dp[i-1][0])
return dp[-1][1]123.买卖股票的最佳时机III
本题与之前题的区别：最多可以完成 两笔 交易 （买一次还是两次呢）
确定dp数组（dp table）以及下标的含义
dp[i][0] 表示不操作
dp[i][1] 表示第一次持有（可以是延续前一天就已经买入的操作，或者当天买入）
dp[i][2] 表示第一次不持有（可以是延续前一天就已经卖出的操作，也可以是第i天就卖出了）
dp[i][3] 表示第二次持有（可以是延续前一天就已经买入的操作，或者当天买入）
dp[i][4] 表示第二次不持有（可以是延续前一天就已经卖出的操作，也可以是第i天就卖出了）
注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态
很多同学把“持有”和“买入”没区分清楚。
确定递推公式
关键点：看dp[i][0]和dp[i][1]，dp[i][2]，dp[i][3]，dp[i][4]是由哪些状态推出来的
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])
初始化dp数组(可以同一天买入卖出)
当天可以买卖和当天不可以买卖，是一样的
dp[i]与dp[i-1]有关
所以要初始化dp[0]和dp[0]
i从1开始遍历
dp[0][0] :0
dp[0][1] :-prices[0] 第0天买入
dp[0][2]:0
dp[0][3]:-prices[0]
dp[0][4]:0
遍历顺序
后面状态依赖前面状态，所以从前往后遍历，i从1开始
class Solution:
def maxProfit(self, prices: List[int]) -> int:
#len(prices) * 5维数组
dp = [[0 for _ in range(5)] for i in range(len(prices))]
#dp[i][0] 不操作，dp[i][1]：第一次持有 ，dp[i][2]：第一次不持有 ，dp[i][3]：第二次持有 ，dp[i][4]： 第二次不持有
dp[0] = [0,-prices[0],0,-prices[0],0]
for i in range(1,len(prices)):
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][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] #这个结果包含了第一次买卖的最大值如果第一次卖出已经是最大值了，那么我们可以在当天立刻买入再立刻卖出。所以dp[4][4]已经包含了dp[4][2]的情况。也就是说第二次卖出手里所剩的钱一定是最多的
标签：max,买卖,持有,股票,最佳时机,买入,prices,dp From： https://blog.csdn.net/qq_52149213/article/details/139482081