思路：

        股票买卖，首先要定义好顺序，只有先买了才能卖出。对于第i天，状态可以是持有股票或者不持有股票。如dp[i][0]表示第i天持有股票，dp[i][1]表示第i天不持有股票。

状态转移：

（1）第i天持有：dp[i][0]=max(继承自前一天持有，前一天不持有而今天买入

        即：dp[i][0]=max(dp[i-1][0],-pricces[i])

（2）第i天不持有：dp[i][1]=max(继承自前一天不持有，前一天持有而今天卖出)

         即：dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])

1.买卖股票的最佳时机

        只允许买卖一次

#第一种写法：动态规划
def maxProfit(prices):
    #dp[i][0]表示第i天持有  dp[i][1]表示第i天不持有
    n=len(prices)
    dp=[[0]*2 for _ in range(n) ]
    dp[0][0]=-prices[0]  #最初始持有的状态
    for i in range(1,n):
        dp[i][0]=max(dp[i-1][0],-prices[i])#持有，只允许买卖一次，是第一次买，是-prices[i]
        dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])  #不持有
    return dp[-1][1]
#第二种写法：贪心思想
# def maxProfit(prices):
#     if not prices:
#         return 0
#     n=len(prices)
#     max_profit=0
#     minprice=prices[0]
#     for i in range(n):
#         minprice=min(minprice,prices[i])  #记录当前的最低价
#         max_profit=max(max_profit,prices[i]-minprice)  #用当天的价格减去当前最低价
#     return max_profit
def main():
    prices=list(map(int,input().split()))
    res=maxProfit(prices)
    print(res)
if __name__=="__main__":
    main()

2.买卖股票时机2

        可以买卖多次。和买卖股票1的区别就是，在计算买入股票价格时，当前的现金和之前获得的利润有关，变成了dp[i-1][1]-prices[i]（这一行代码是唯一区别）。而买卖股票1是0-prices[i]，因为只允许买卖一次，所以在买之前手上的现金为0。

def maxProfit(prices):
    if not prices:
        return 0
    n=len(prices)
    dp=[[0]*2 for i in range(n)]
    dp[0][0]=-prices[0]  #最初始持有的状态
    dp[0][1]=0
    for i in range(1,n):
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i])#第i天持有，因为可以买卖多次，所以这里的利润是dp[i-1][1]-prices[i]
        dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])#第i天不持有
    return dp[-1][1]
def main():
    prices=list(map(int,input().split()))
    res=maxProfit(prices)
    print(res)
if __name__=="__main__":
    main()

3.买卖股票的时机3

        最多可以买卖两次股票。状态拆分：第一次持有，第一次不持有，第二次持有，第二次不持有。也就是每一天可能是以上四种状态之一。

具体表示为：

第i天第一次持有：dp[i][0]=max(继承自上一天第一次持有，上一天第一次不持有但今天买入)

                              dp[i][0]=max(dp[i-1][0],0-prices[i])

第i天第一次不持有：dp[i][1]=max(继承自上一天第一次不持有，上一天第一次持有但今天卖出)

                                 dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])

第i天第二次持有：dp[i][2]=max(继承自上一天第二次持有，上一天第一次不持有但今天买入)

                              dp[i][2]=max(dp[i-1][2],dp[i-1][1]-prices[i])

第i天第二次不持有：dp[i][3]=max(继承自上一天第二次不持有，上一天第二次持有但今天卖出)

                                 dp[i][3]=max(dp[i-1][3],dp[i-1][2]+prices[i])

def maxProfit(prices):
    if not prices:
        return 0
    n = len(prices)
    # 每天 4 个状态：第一次持股、第一次不持股、第二次持股、第二次不持股
    dp = [[0] * 4 for _ in range(n)]
    # 初始化第一天
    dp[0][0] = -prices[0]
    dp[0][2] = -prices[0]
    for i in range(1, n):
        dp[i][0] = max(dp[i - 1][0], -prices[i])  # 第 i 天第一次持股
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])  # 第 i 天第一次不持股
        dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i])  # 第 i 天第二次持股
        dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i])  # 第 i 天第二次不持股

    return dp[-1][3]  # 第二次卖出，也就是第二次不持股，收益是最大的
def main():
    prices = list(map(int, input().split()))
    if not prices:
        return 0
    res = maxProfit(prices)
    print(res)
if __name__ == "__main__":
    main()

4.买卖股票的时机4

        最多允许k次买卖。和买卖股票3的区别是，这里要使用一个循环来控制交易次数k。同时要特殊处理一下第一次持股的情况。

def maxProfit(k,prices):
    if not prices or k==0:
        return 0
    n=len(prices)
    dp=[[0]*(2*k) for _ in range(n)]
    for j in range(0,2*k-1,2):  #初始化
        dp[0][j]=-prices[0]
    for i in range(1,n):
        for j in range(0,2*k-1,2):
            #持股
            if j==0:   #单独处理一下第一次持股的状态
                dp[i][j]=max(dp[i-1][j],-prices[i])  #因为还没有利润，所以是-prices[i]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i-1][j-1]-prices[i])  #用前面累加的利润，减去买股票的钱
            #不持股
            dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]+prices[i])
    return dp[-1][2*k-1]
def main():
    k=int(input())
    prices=list(map(int,input().split()))
    res=maxProfit(k,prices)
    print(res)
if __name__=="__main__":
    main()