买卖股票的最佳时机 II

读前福利，送大家一些电子书

买卖股票的最佳时机 II

LeetCode 122. 买卖股票的最佳时机 II

问题描述

给定一个数组 prices，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

分析问题

这个问题的解题思路和上题类似，也是“多阶段决策最优”问题。也符合动态规划解题模型。不过这里的“状态”会有所区别，我们来看一下。考虑到 “不能同时参与多笔交易”。所以，每天交易结束后手里只可能存在有股票和没有股票两种状态。所以，我们可以用二个数组来表示，其中dp1[i]表示第i天交易后，手里没有股票的最大利润。dp2[i]表示第i天交易完成后，手里有股票的最大利润。

dp1[i]表示第i天手里没有股票的最大利润，那么这个状态要么是由dp1[i-1]，即前一天手里没有股票的最大利润，转移过来。要么由dp2[i-1]+prices[i]，即前一天手里有股票，今天把这个股票卖出。所以dp1[i]的状态转移方程为：

dp1[i]=max(dp1[i-1],dp2[i-1]+prices[i])

dp2[i]表示第i天手里有股票的最大利润，那么这个状态要么是由dp2[i-1]，即前一天手里有股票的最大利润，转移过来。要么由dp1[i-1]-prices[i]，即前一天手里没有股票，今天把这个股票进行买入。所以dp2[i]的状态转移方程为：

dp2[i]=max(dp2[i-1],dp1[i-1]-prices[i])

所以我们代码实现如下所示：

def maxProfit(prices):
    n=len(prices)
    if n==0:
        return 0
    dp1=[0]*n
    dp2=[0]*n
    #手里没有股票
    dp1[0]=0
    #手里有股票
    dp2[0]=-prices[0]
    for i in range(1,n):
        dp1[i]=max(dp1[i-1],dp2[i-1]+prices[i])
        dp2[i]=max(dp2[i-1],dp1[i-1]-prices[i])

    return dp1[n-1]

prices=[7, 1, 5, 3, 6, 4]
print(maxProfit(prices))