题解 | #买卖股票的最好时机#

买卖股票的最好时机

http://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec

python版动态规划题解,更改k适用于任意交易次数

class Solution:
    def maxProfit(self,prices):
        #适用于任意交易次数,只用于本题可以将k维去掉
        len_i=len(prices)  #能交易的总天数
        k=1  #允许交易的最大次数
        len_k=k+1  #如果交易一次,k应该有0和1两个值!!!!!!!!
        dp=[[[0]*2 for _ in range(len_k)] for _ in range(len_i)] #dp[交易的第几天][最多交易k次][手里持有或没有持有股票]
        #base case
        #dp[-1][k][0]=0  还没开始交易的最大利润是0
        #dp[-1][k][1]=-float('inf')  还没开始交易手里不可能出现股票
        #dp[i][0][0]=0  不允许交易的话最大利润肯定是0
        #dp[i][0][1]=-float('inf')  不允许交易手中不可能有股票
        #处理basecase
        # i=0的情况
        for k in range(len_k):
            dp[0][k][0]=0
            dp[0][k][1]=-prices[0]
        #k=0的情况
        for i in range(len_i):
            dp[i][0][0]=0
            dp[i][0][1]=-prices[i]

        for i in range(1,len(dp)):
            for k in range(1,len(dp[0])):
                #第i天手里没有股票的最大利润=max(昨天我就没有,昨天我有我卖了)
                dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
                #第i天手里有股票的最大利润=max(昨天我就有,昨天我没有但是我今天买了)
                dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
        print(dp)
        return dp[-1][-1][0]
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 11:27
明天又是董事长面,啥时候是个头啊
积极向上的林同学:董事长亲自面试
点赞 评论 收藏
分享
06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务