动态规划----多阶段决策过程

• 阶段 1：第一次买之前
• 阶段 2：持有股票（第一次买之后，但还没卖）
• 阶段 3：第一次卖之后且第二次买之前
• 阶段 4：持有股票（第二次买之后，但还没卖）
• 阶段 5：第二次卖之后

在这种情况下，如果今天想买股票，需要知道前一天处于什么阶段。

如：前一天处在“阶段 2”，那今天就有两种可能的决策：

• 1、卖掉前一天买入的股票，不买。----> 进入阶段 3
• 2、卖掉前一天买入的股票，立即买入----> 进入阶段 4

如果前一天处在“阶段 3”，则今天只能买 或者 不买：

• 买 ----> 进入阶段 4
• 不买 ----> 停在阶段 3

此题最优策略一定是前N天结束后，处于

• 阶段 1： 没买卖过
• 阶段 3： 买卖 1 次
• 阶段 5： 买卖 2 次

因为如果持有股票不卖，不能获利，而本题要求获利最大，因此不能处在阶段 3 和 阶段 4。

例如1：在第N天（前 N-1 天结束）处在阶段 5 的最大获利为: dp[N][5]

• 情况 1： 前一天已经处在阶段 5 了，那今天就不用动，获利跟前一天一样，前一天在阶段 5的最大获利为： dp[N-1][5]

• 情况 2： 前一天处在阶段 4（第二次持有股票），那今天就卖掉股票，进入阶段 5，则今天的获利：

  dp[N][5] = dp[N-1][4] + (P[N-1] - P[N-2])

  即：前一天所处阶段的最大获利 + 持有的股票的利润（每多持有一天，就多一天的红利（可能为负））

同上，例如2，在阶段 4的最大获利，dp[N][4]

• 情况 1： 前一天已经处在阶段 4，则今天的获利为：dp[N-1][4] + (P[N-1] - P[N-2])--括号里为今天的红利
• 情况 2： 前一天处在阶段 3，因为当前处于阶段 4，所以是今天刚买，刚买还没有红利，所以其获利为：dp[N-1][3]
• 情况 3： 前一天还在阶段 2，今天直接卖掉立马买入而进入阶段 4，则获利为：dp[N-1][2] + (P[N-1] - P[N-2])

初始条件： 刚开始 第0天处于阶段1，

• dp[0][1] = 0
• dp[0][2] = dp[0][3] = dp[0][4] = dp[0][5] = -float('inf')

状态转移方程：

• 对于阶段 1、3、5（例如1）：

  dp[i][j] = max{dp[i-1][j], dp[i-1][j-1] + (P[N-1] - P[N-2])}

• 对于阶段 2、4（例如2）：

  dp[i][j] = max{dp[i-1][j] + (P[N-1] - P[N-2]), dp[i-1][j-1], dp[i-1][j-2] + (P[N-1] - P[N-2])}

• 注意：若下标越界成了负号，则不计入max项。又因为最多买卖2次，所以最大获利一定是清仓状态，即:

  max{dp[N][1], dp[N][3], dp[N][5]}

下面附上代码：

import sys

inputs = []
for line in sys.stdin:
    a = line.split()
    inputs.append(a)
    
n = int(inputs[0][0])
P = [int(x) for x in inputs[1]]

dp = [[0] * (5 + 1) for _ in range(n + 1)]

# 初始条件
dp[0][1] = 0
dp[0][2] = dp[0][3] = dp[0][4] = dp[0][5] = -float('inf')

for i in range(1, n + 1):
    # 1, 3, 5
    for j in (1, 3, 5):
        # dp[i][j] = max{dp[i-1][j], dp[i-1][j-1] + (P[N-1] - P[N-2])}
        dp[i][j] = dp[i-1][j]
        if j > 1 and i >= 2 and dp[i-1][j-1] != -float('inf'):
            dp[i][j] = max(dp[i][j], dp[i-1][j-1] + (P[i-1] - P[i-2]))
    
    # 2, 4
    for j in (2, 4):
        # dp[i][j] = max{dp[i-1][j] + (P[N-1] - P[N-2]), dp[i-1][j-1], dp[i-1][j-2] + (P[N-1] - P[N-2])}
        dp[i][j] = dp[i-1][j-1]
        if i > 1 and dp[i-1][j] != -float('inf'):
            dp[i][j] = max(dp[i][j], dp[i-1][j] + (P[i-1] - P[i-2]))
            
        if j > 2 and i >= 2 and dp[i-1][j-2] != -float('inf'):
            dp[i][j] = max(dp[i][j], dp[i-1][j-2] + (P[i-1] - P[i-2]))
    
print(max(dp[n][1], dp[n][3], dp[n][5]))