嘉义县网站建设_网站建设公司_UI设计师_seo优化

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])