121. 买卖股票的最佳时机
看上去用贪心的方法比较简单，找到一个极小值后的极大值，做差即可。然而出在动态规划这里，好好思考一下：
——动态规划数组的意义
dp = [[0]*2 for i in range(n+1)]也即对于第0天到第n天，【0】位置代表第i天，dp[i][j]所能获得的最大利润，【1】位置代表此时持有股票的状态 0或1。
——状态转移方程
dp[i][0] = max(dp[i-1][0] , dp[i-1][1] + prices[i-1]) dp[i][1] = max(dp[i-1][1] , -prices[i-1])
可能出现的状态如上图所示
相对应的情况如下：
如果第i天有股票，那么由昨天本来就有和昨天没有，买入两种情况的最大值
如果第i天无股票，那么由昨天本来就没有和昨天有，卖出两种情况的最大值
但是要注意，因为只会购买并出售一次，注意一个问题：
dp[i][1] = max(dp[i-1][1] , -prices[i-1])，也即出售之后，不再进入下一次递归，而是直接结束
——初始化
注意要初始化dp[0][1] = -inf，因为在第0天拥有股票是不合法的，解释如图
注意price数组和dp数组存在的索引偏移
——遍历顺序
顺序遍历
class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) dp = [[0]*2 for i in range(n+1)] dp[0][1] = -inf for i in range(1,n+1): dp[i][0] = max(dp[i-1][0] , dp[i-1][1] + prices[i-1]) dp[i][1] = max(dp[i-1][1] , -prices[i-1]) return dp[n][0]122.买卖股票的最佳时机II
该题和上题的区别就是可以多次买卖，区别只有状态转移方差中有股票的情况
——动态规划数组的意义
dp = [[0]*2 for i in range(n+1)]也即对于第0天到第n天，【0】位置代表第i天，dp[i][j]所能获得的最大利润，【1】位置代表此时持有股票的状态 0或1。
——状态转移方程
dp[i][0] = max(dp[i-1][0] , dp[i-1][1] + prices[i-1]) dp[i][1] = max(dp[i-1][1] , dp[i-1][0] - prices[i-1])
可能出现的状态如上图所示
相对应的情况如下：
如果第i天有股票，那么由昨天本来就有和昨天没有，买入两种情况的最大值
如果第i天无股票，那么由昨天本来就没有和昨天有，卖出两种情况的最大值
——初始化
注意要初始化dp[0][1] = -inf，因为在第0天拥有股票是不合法的，解释如图
注意price数组和dp数组存在的索引偏移
——遍历顺序
顺序遍历
class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) dp = [[0]*2 for _ in range(n+1)] dp[0][1] = -inf for i in range(1,n+1): dp[i][0] = max(dp[i-1][0] , dp[i-1][1] + prices[i-1]) dp[i][1] = max(dp[i-1][1] , dp[i-1][0] - prices[i-1]) return dp[n][0]123.买卖股票的最佳时机III
补充一点数组构造知识：
dp = [[0]*5 for _ in range(n+1)]这行代码通过列表推导式（List Comprehension）构建了一个二维数组
[0]*5创建内层一维数组
生成一个包含5个0的列表，例如
[0, 0, 0, 0, 0]。
for _ in range(n+1)控制外层循环次数
循环
n+1次，每次循环生成上述一维数组。整个列表推导式
组合成二维数组
将每次循环生成的一维数组作为元素，组合成一个新的外层列表。
错误示范：初学者可能会写成dp = [[0] * 5] * (n+1)。使用*运算符复制一个包含可变对象（如列表）的列表时，复制的是对象的引用而非对象本身的副本
dp = np.zeros((n+1, 5))np库中也有可用的内容
——dp数组的意义
dp = [[0]*5 for _ in range(n+1)]
[[0, -inf, -inf, -inf, -inf], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]其中每个维度上有5种状态表式如下图：
0——无状态
1——第一次持有股票
2——第一次售出股票后（第一次不持有股票）
3——第二次持有股票
4——第二次售出股票后（第二次不持有股票）
——状态转移方程
dp[i][0] = dp[i-1][0] dp[i][1] = max(dp[i-1][1] , dp[i-1][0]-prices[i-1]) dp[i][2] = max(dp[i-1][2] , dp[i-1][1]+prices[i-1]) dp[i][3] = max(dp[i-1][3] , dp[i-1][2]-prices[i-1]) dp[i][4] = max(dp[i-1][4] , dp[i-1][3]+prices[i-1])——初始化
for j in range(1, 5):
dp[0][j] = -inf
—— [0, -inf, -inf, -inf, -inf],
也即不可能在第0天产生1、2、3、4状态
——遍历顺序
正向遍历
import numpy as np #导入numpy库 class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) dp = [[0]*5 for _ in range(n+1)] for j in range(1, 5): dp[0][j] = -inf print(dp) for i in range(1, n+1): dp[i][0] = dp[i-1][0] dp[i][1] = max(dp[i-1][1] , dp[i-1][0]-prices[i-1]) dp[i][2] = max(dp[i-1][2] , dp[i-1][1]+prices[i-1]) dp[i][3] = max(dp[i-1][3] , dp[i-1][2]-prices[i-1]) dp[i][4] = max(dp[i-1][4] , dp[i-1][3]+prices[i-1]) return max(dp[n][0], dp[n][2], dp[n][4])
