企业官网建设流程全解析

企业网站建设的经费预算,公司运营方案模板,wordpress 应用店商,9免费建网站121. 买卖股票的最佳时机 看上去用贪心的方法比较简单#xff0c;找到一个极小值后的极大值#xff0c;做差即可。然而出在动态规划这里#xff0c;好好思考一下#xff1a;——动态规划数组的意义dp [[0]*2 for i in range(n1)]也即对于第0天到第n天#xff0c;【0】位置…121. 买卖股票的最佳时机看上去用贪心的方法比较简单找到一个极小值后的极大值做差即可。然而出在动态规划这里好好思考一下——动态规划数组的意义dp [[0]*2 for i in range(n1)]也即对于第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(n1)] dp[0][1] -inf for i in range(1,n1): 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(n1)]也即对于第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(n1)] dp[0][1] -inf for i in range(1,n1): 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(n1)]这行代码通过列表推导式List Comprehension构建了一个二维数组[0]*5创建内层一维数组生成一个包含5个0的列表例如[0, 0, 0, 0, 0]。for _ in range(n1)控制外层循环次数循环n1次每次循环生成上述一维数组。整个列表推导式组合成二维数组将每次循环生成的一维数组作为元素组合成一个新的外层列表。错误示范​初学者可能会写成dp [[0] * 5] * (n1)。使用*运算符复制一个包含可变对象​如列表的列表时复制的是对象的引用而非对象本身的副本dp np.zeros((n1, 5))np库中也有可用的内容——dp数组的意义dp [[0]*5 for _ in range(n1)][[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(n1)] for j in range(1, 5): dp[0][j] -inf print(dp) for i in range(1, n1): 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])