ToB企服应用市场:ToB评测及商务社交产业平台

标题: 动态规划 之 状态机dp [打印本页]
作者: 反转基因福娃    时间: 2025-2-19 13:22
标题: 动态规划 之 状态机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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4