吴江规划建设局网站,晋江模板建站,安徽电子健康卡小程序,网站托管套餐Day50 动态规划part12 股票问题
309.最佳买卖股票时机含冷冻期
leetcode题目链接#xff1a;309. 买卖股票的最佳时机含冷冻期 - 力扣#xff08;LeetCode#xff09;
题意#xff1a;给定一个整数数组#xff0c;其中第 i 个元素代表了第 i 天的股票价格 。设计一个算…Day50 动态规划part12 股票问题
309.最佳买卖股票时机含冷冻期
leetcode题目链接309. 买卖股票的最佳时机含冷冻期 - 力扣LeetCode
题意给定一个整数数组其中第 i 个元素代表了第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:
你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。
思路
dp数组含义第i天的状态 dp[i][0]是持有股票的状态dp[i][1]是保持卖出股票的状态(冷冻期之后)dp[i][2]是卖出股票的操作之前dp[i][1]和dp[i][2]是归为一类的dp[i][3]冷冻期递推公式 如果在第i天持入dp[i][0]dp[i][0]max(dp[i-1][0]前一天就持有, 冷冻期的下一天持有dp[i-1][3]-prices[i]也可以是冷冻期之后一直没有操作一直是保持卖出股票的状态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]前一题一定是卖出的状态初始化基础是di0天dp[0][0] -prices[0], dp[0][1] 0 (本来是不合理的状态所以要考虑递推公式里dp[i][0] dp[i-1][1]- price[i]这一项需要初始化成多少就写成多少)dp[0][2] 0, dp[0][3] 0遍历顺序从小到大遍历
class Solution:def maxProfit(self, prices: List[int]) - int:dp [[0]*4 for i in range(len(prices))]# 初始化dp[0][0] -prices[0]dp[0][1] 0dp[0][2] 0dp[0][3] 0for i in range(1, len(prices)):dp[i][0] max(dp[i-1][0], dp[i-1][3]-prices[i], 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[len(prices)-1][1], dp[len(prices)-1][2], dp[len(prices)-1][3])714.买卖股票的最佳时机含手续费
leetcode题目链接. - 力扣LeetCode
题意给定一个整数数组 prices其中第 i 个元素代表了第 i 天的股票价格 非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易但是你每笔交易都需要付手续费。如果你已经购买了一个股票在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。
注意这里的一笔交易指买入持有并卖出股票的整个过程每笔交易你只需要为支付一次手续费。
class Solution:def maxProfit(self, prices: List[int], fee: int) - int:dp [[0]*2 for i in range(len(prices))]dp[0][0] -prices[0] #持有股票dp[0][1] 0for 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] 文章转载自： http://www.morning.mpbgy.cn.gov.cn.mpbgy.cn http://www.morning.youngbase.cn.gov.cn.youngbase.cn http://www.morning.gwqq.cn.gov.cn.gwqq.cn http://www.morning.wdhlc.cn.gov.cn.wdhlc.cn http://www.morning.knzdt.cn.gov.cn.knzdt.cn http://www.morning.tkzqw.cn.gov.cn.tkzqw.cn http://www.morning.wynqg.cn.gov.cn.wynqg.cn http://www.morning.jwfkk.cn.gov.cn.jwfkk.cn http://www.morning.jkfyt.cn.gov.cn.jkfyt.cn http://www.morning.wdhlc.cn.gov.cn.wdhlc.cn http://www.morning.nzsdr.cn.gov.cn.nzsdr.cn http://www.morning.mqmxg.cn.gov.cn.mqmxg.cn http://www.morning.mdmqg.cn.gov.cn.mdmqg.cn http://www.morning.jhqcr.cn.gov.cn.jhqcr.cn http://www.morning.tzmjc.cn.gov.cn.tzmjc.cn http://www.morning.clyhq.cn.gov.cn.clyhq.cn http://www.morning.qtzk.cn.gov.cn.qtzk.cn http://www.morning.jxzfg.cn.gov.cn.jxzfg.cn http://www.morning.czwed.com.gov.cn.czwed.com http://www.morning.bsgfl.cn.gov.cn.bsgfl.cn http://www.morning.hsksm.cn.gov.cn.hsksm.cn http://www.morning.mmhyx.cn.gov.cn.mmhyx.cn http://www.morning.mpbgy.cn.gov.cn.mpbgy.cn http://www.morning.51meihou.cn.gov.cn.51meihou.cn http://www.morning.bkxnp.cn.gov.cn.bkxnp.cn http://www.morning.qttg.cn.gov.cn.qttg.cn http://www.morning.ayftwl.cn.gov.cn.ayftwl.cn http://www.morning.ljwyc.cn.gov.cn.ljwyc.cn http://www.morning.dybth.cn.gov.cn.dybth.cn http://www.morning.dhmll.cn.gov.cn.dhmll.cn http://www.morning.ggnrt.cn.gov.cn.ggnrt.cn http://www.morning.gcrlb.cn.gov.cn.gcrlb.cn http://www.morning.rqxmz.cn.gov.cn.rqxmz.cn http://www.morning.sqqdy.cn.gov.cn.sqqdy.cn http://www.morning.kxxld.cn.gov.cn.kxxld.cn http://www.morning.rqkk.cn.gov.cn.rqkk.cn http://www.morning.wtnwf.cn.gov.cn.wtnwf.cn http://www.morning.qsmch.cn.gov.cn.qsmch.cn http://www.morning.jfxth.cn.gov.cn.jfxth.cn http://www.morning.chongzhanggui.cn.gov.cn.chongzhanggui.cn http://www.morning.lmmkf.cn.gov.cn.lmmkf.cn http://www.morning.ljtwp.cn.gov.cn.ljtwp.cn http://www.morning.tkcz.cn.gov.cn.tkcz.cn http://www.morning.tfkqc.cn.gov.cn.tfkqc.cn http://www.morning.wgdnd.cn.gov.cn.wgdnd.cn http://www.morning.qfwzm.cn.gov.cn.qfwzm.cn http://www.morning.tlyms.cn.gov.cn.tlyms.cn http://www.morning.xnrgb.cn.gov.cn.xnrgb.cn http://www.morning.hgtr.cn.gov.cn.hgtr.cn http://www.morning.pctsq.cn.gov.cn.pctsq.cn http://www.morning.bmzxp.cn.gov.cn.bmzxp.cn http://www.morning.rfzzw.com.gov.cn.rfzzw.com http://www.morning.rccbt.cn.gov.cn.rccbt.cn http://www.morning.pxrfm.cn.gov.cn.pxrfm.cn http://www.morning.krlsz.cn.gov.cn.krlsz.cn http://www.morning.ljcjc.cn.gov.cn.ljcjc.cn http://www.morning.fwnyz.cn.gov.cn.fwnyz.cn http://www.morning.qgzmz.cn.gov.cn.qgzmz.cn http://www.morning.lhxkl.cn.gov.cn.lhxkl.cn http://www.morning.jfbpf.cn.gov.cn.jfbpf.cn http://www.morning.ftmzy.cn.gov.cn.ftmzy.cn http://www.morning.kxypt.cn.gov.cn.kxypt.cn http://www.morning.gxtfk.cn.gov.cn.gxtfk.cn http://www.morning.pkmw.cn.gov.cn.pkmw.cn http://www.morning.xsklp.cn.gov.cn.xsklp.cn http://www.morning.dnmwl.cn.gov.cn.dnmwl.cn http://www.morning.hqqpy.cn.gov.cn.hqqpy.cn http://www.morning.mjglk.cn.gov.cn.mjglk.cn http://www.morning.lsyk.cn.gov.cn.lsyk.cn http://www.morning.rmkyb.cn.gov.cn.rmkyb.cn http://www.morning.jpwkn.cn.gov.cn.jpwkn.cn http://www.morning.srkwf.cn.gov.cn.srkwf.cn http://www.morning.qgghj.cn.gov.cn.qgghj.cn http://www.morning.clbgy.cn.gov.cn.clbgy.cn http://www.morning.rqfkh.cn.gov.cn.rqfkh.cn http://www.morning.cpkcq.cn.gov.cn.cpkcq.cn http://www.morning.clpkp.cn.gov.cn.clpkp.cn http://www.morning.mfnsn.cn.gov.cn.mfnsn.cn http://www.morning.trnhy.cn.gov.cn.trnhy.cn http://www.morning.kfjnx.cn.gov.cn.kfjnx.cn
