栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

最佳买卖股票时机含冷冻期-动态规划309-python

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

最佳买卖股票时机含冷冻期-动态规划309-python

没看答案,可以交易无数次,但是卖出后的第二天不可以买入。

labuladong版(超时)

import sys

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = k = len(prices)

        dp = [[[0] * 2 for _ in range(k+1)] for _ in range(n+1)]
        for i in range(n):
            dp[i][0][0] = 0
            dp[i][0][1] = -sys.maxsize
        for j in range(k+1):
            dp[-1][j][0] = 0
            dp[-1][j][1] = -sys.maxsize
        
        for i in range(n):
            for j in range(1, k+1):
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-2][j-1][0] - prices[i])
        
        return dp[n-1][k][0]

简化版(省略k)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)

        dp = [[0] * 2 for _ in range(n+1)]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])

            if i > 1:
                dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
            else:
                dp[i][1] = max(dp[i-1][1], -prices[i])
        
        return dp[n-1][0]
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/966439.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号