宿迁做网站哪家公司好,做网站外包公司名称大全,做网站后台的叫什么,购物网站支付页面制作309.最佳买卖股票时机含冷冻期 本题加了一个冷冻期#xff0c;状态就多了#xff0c;有点难度#xff0c;大家要把各个状态分清#xff0c;思路才能清晰 视频讲解#xff1a;动态规划来决定最佳时机#xff0c;这次有冷冻期#xff01;| LeetCode#xff1a;309.买卖… 309.最佳买卖股票时机含冷冻期 本题加了一个冷冻期状态就多了有点难度大家要把各个状态分清思路才能清晰 视频讲解动态规划来决定最佳时机这次有冷冻期| LeetCode309.买卖股票的最佳时机含冷冻期_哔哩哔哩_bilibili 代码随想录 思路 还是用的之前的方法就是多加了个冷冻期。 class Solution(object):def maxProfit(self, prices):lengthlen(prices)if length%31:caselengthdeglength//3elif length%30:caselength1deglength//3else:caselength1deglength//31#deg表示要初始化的数量#case表示最大有几种情况dp[[0]*case for _ in range(len(prices))]i1 #表示初始化的起始量while deg!0: #进行初始化dp[0][i]-prices[0]i3deg-1for i in range(1,length):dp[i][0]dp[i-1][0]for j in range(1,case):if j%31: #表示持有的时候dp[i][j]max(dp[i-1][j],dp[i-1][j-1]-prices[i])elif j%32: #表示未持有的时候dp[i][j]max(dp[i-1][j],dp[i-1][j-1]prices[i])else: #表示冷冻期的时候dp[i][j]dp[i-1][j-1]return max(dp[-1]) 答案 class Solution:def maxProfit(self, prices: List[int]) - int:n len(prices)if n 0:return 0dp [[0] * 4 for _ in range(n)] # 创建动态规划数组4个状态分别表示持有股票、不持有股票且处于冷冻期、不持有股票且不处于冷冻期、不持有股票且当天卖出后处于冷冻期dp[0][0] -prices[0] # 初始状态第一天持有股票的最大利润为买入股票的价格for i in range(1, n):dp[i][0] max(dp[i-1][0], max(dp[i-1][3], dp[i-1][1]) - prices[i]) # 当前持有股票的最大利润等于前一天持有股票的最大利润或者前一天不持有股票且不处于冷冻期的最大利润减去当前股票的价格dp[i][1] max(dp[i-1][1], dp[i-1][3]) # 当前不持有股票且处于冷冻期的最大利润等于前一天持有股票的最大利润加上当前股票的价格dp[i][2] dp[i-1][0] prices[i] # 当前不持有股票且不处于冷冻期的最大利润等于前一天不持有股票的最大利润或者前一天处于冷冻期的最大利润dp[i][3] dp[i-1][2] # 当前不持有股票且当天卖出后处于冷冻期的最大利润等于前一天不持有股票且不处于冷冻期的最大利润return max(dp[n-1][3], dp[n-1][1], dp[n-1][2]) # 返回最后一天不持有股票的最大利润 总结 虽然说我觉得能写出来就已经不错了但是他的时间和空间都要的很多。答案只有5种状态他没有算次数所以要更简单一些。我的可以成为暴力法了。 714.买卖股票的最佳时机含手续费 相对122.买卖股票的最佳时机II 本题只需要在计算卖出操作的时候减去手续费就可以了代码几乎是一样的可以尝试自己做一做。 视频讲解动态规划来决定最佳时机这次含手续费| LeetCode714.买卖股票的最佳时机含手续费_哔哩哔哩_bilibili 代码随想录 class Solution(object):def maxProfit(self, prices, fee):#0.表示持有股票的时候#1.表示没有持有股票的时候dp[[0]*2 for _ in range(len(prices))]dp[0][0]-prices[0]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]-fee)return dp[-1][1] 总结 也算是复习了一下股票第四种题的答案写起来不算难。 股票总结 股票问题做一个总结吧 代码随想录 总结 我感觉股票问题最重要的是找到所有的状态知道套路了其实还算简单。
