动态规划 之 状态机dp

状态机DP：一样平常dp[j]表如今数组a[:i]的时候状态j的最优值
  买卖股票

121.买卖股票的最佳机会

121.买卖股票的最佳机会

   思绪分析：对于这题，我们只需罗列卖出的股票的价格prices，同时记录先前的最小的买入价格minprice 是 prices[0] 到 prices[i-1]的最小值

1. class Solution:
2.     def maxProfit(self, prices: List[int]) -> int:
3.         ans = 0
4.         min_price = prices[0]
5.         for p in prices:
6.             ans = max(ans, p - min_price)
7.             min_price = min(min_price, p)
8.         return ans

复制代码

122.买卖股票的最佳机会 II

122.买卖股票的最佳机会 II

   思绪分析：对于每一天来说，是不是具有两个状态持有股票和不持有股票？，那么我们就定义dp[0]和dp[1]表如今第i天不持有和持有股票，在每一天，每一个状态都可以由前一天的全部状态转移而来！

1. class Solution:
2.     def maxProfit(self, prices: List[int]) -> int:
3.         # 状态机，对于每一天来说，存在两个状态，也就是持有股票与不持有股票
4.         n = len(prices)
5.         # dp[i][0]表示在第i天没有持有股票的最大收益,dp[i][1]表示在第i天持有股票的最大收益
6.         dp = [[0]*2 for i in range(n+1)]
7.         dp[0][0] = 0
8.         # 不可能持有股票的
9.         dp[0][1] = -float('inf')
10.         for i in range(n):
11.             # 原本dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])
12.             dp[i+1][0] = max(dp[i][0],dp[i][1]+prices[i])
13.             # 原本dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])
14.             dp[i+1][1] = max(dp[i][1],dp[i][0]-prices[i])
15.         # 最大的收益就是第n天不持有股票的场景
16.         return dp[n][0]

复制代码

123.买卖股票的最佳机会III

123.买卖股票的最佳机会III

   思绪分析：这题是 188.买卖股票的最佳机会III的k=2的场景

1. class Solution:
2.     def maxProfit(self, prices: List[int]) -> int:
3.         # 参照买卖股票的最佳时机IV
4.         k = 2
5.         n = len(prices)
6.         dp = [[[-float('inf')]*2 for _ in range(k+2)] for _ in range(n+1)]
7.         # 初始化
8.         for i in range(1,k+2):
9.             dp[0][i][0] = 0
10.         for i in range(n):
11.             for j in range(1,k+2):
12.                 # j 表示已经交易了j-1次
13.                 # dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1]+prices[i])
14.                 dp[i+1][j][0] = max(dp[i][j][0],dp[i][j][1]+prices[i])
15.                 # dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i])
16.                 dp[i+1][j][1] = max(dp[i][j][1],dp[i][j-1][0]-prices[i])
17.         return dp[n][k+1][0]

复制代码

188.买卖股票的最佳机会 IV

188.买卖股票的最佳机会 IV

   思绪分析：加多一个参数表现当前交易的次数
    注意这个初始化

1.         dp = [[[-float('inf')]*2 for _ in range(k+2)] for i in range(n+1)]
2.         # 初始化dp[0][k][1]= -inf
3.         for i in range(1,k+2):
4.             dp[0][i][0] = 0
5.             

复制代码

  错误的初始化

1.         dp = [[[0]*2 for _ in range(k+2)] for i in range(n+1)]
2.         # 初始化dp[0][k][1]= -inf
3.         for i in range(1,k+2):
4.             dp[0][i][1] = 0

复制代码

1. class Solution:
2.     def maxProfit(self, k: int, prices: List[int]) -> int:
3.         # 要增加一个参数，表示当前可以交易的次数
4.         # dp[i][k][j] 表示在第i天持有股票在第k次交易,j=0表示不持有股票的最大收益，j=1表示持有股票的最大收益
5.         n = len(prices)
6.         dp = [[[-float('inf')]*2 for _ in range(k+2)] for i in range(n+1)]
7.         # 初始化dp[0][k][1]= -inf
8.         for i in range(1,k+2):
9.             dp[0][i][0] = 0
10.         # 定义买入股票的时候才会+1交易数
11.         for i in range(n):
12.             for j in range(1,k+2):
13.                 # j 表示已经交易了j-1次
14.                 # dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1]+prices[i])
15.                 dp[i+1][j][0] = max(dp[i][j][0],dp[i][j][1]+prices[i])
16.                 # dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i])
17.                 dp[i+1][j][1] = max(dp[i][j][1],dp[i][j-1][0]-prices[i])
18.         
19.         return dp[n][k+1][0]

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。