1. class Solution:
  2.     def maxProfit(self, prices: List[int]) -> int:
  3.         sell =0
  4.         buy =-prices[0]
  5.         for p in prices[1:]:
  6.             sell =sell if sell>buy+p else buy+p
  7.             buy =buy if buy > -p else -p
  8.         return sell

自己写的比大小所画的时间要小于自带的max函数

动态规划

状态定义

dp[i][j][0/1] 表示第i天 ， 最多进行j次交易，是否有股票,的最大利润

状态转移

dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1]+price[i])
前一天没有股票,交易次数不变
前一天有股票选择卖出,交易次数不变

dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j-1][0]-price[i])
前一天有股票
前一天没有股票选择买入，交易次数减少1

边界条件

天数从第一天开始计算
dp[0][0][0]=0
dp[0][0][1]=0

最后目标

dp[n][k][0]:在第n天 最大交易次数为k时，手中没有股票的最大利润

  1. class Solution:
  2.     def maxProfit(self, prices: List[int]) -> int:
  3.         n = len(prices)
  4.         max_tran = 2
  5.         dp =[[ [0]*2 for _ in range (max_tran)] for _ in range(n)]
  6.         for j in range(max_tran):
  7.             dp[0][j][1]=-prices[0]
  8.         print(dp)
  9.         for i in range(1,n):
  10.             for j in range(max_tran-1,-1,-1):
  11.                dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]) 
  12.                dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i])
  13.             print(dp)
  14.         return dp[n-1][1][0]

问题记录
不是边界问题：
交易次数的作用： 

  1. class Solution:
  2.     def maxProfit(self, prices: List[int]) -> int:
  3.         n = len(prices)
  4.         max_tran = 2
  5.         dp =[[ [0]*2 for _ in range (max_tran+1)] for _ in range(n)]
  6.         for i in range(n):
  7.             for j in range(max_tran,0,-1):
  8.                 if not i:
  9.                     dp[i][j][0] = 0;
  10.                     dp[i][j][1] = -prices[i];
  11.                     continue;
  12.                 dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]) 
  13.                 dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i])     
  14.         return dp[n-1][max_tran][0]

给dp 交易次数多设置了一位？
如果不多设置一位？