动态规划之状态机dp

文章目录 买卖股票121.买卖股票的最佳时机122.买卖股票的最佳时机 II123.买卖股票的最佳时机III188.买卖股票的最佳时机 IV

状态机DP：一般dp[i][j]表示在数组a[:i]的时候状态j的最优值

买卖股票 121.买卖股票的最佳时机

121.买卖股票的最佳时机

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

class Solution: def maxProfit(self, prices: List[int]) -> int: ans = 0 min_price = prices[0] for p in prices: ans = max(ans, p - min_price) min_price = min(min_price, p) return ans 122.买卖股票的最佳时机 II

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

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

class Solution: def maxProfit(self, prices: List[int]) -> int: # 状态机，对于每一天来说，存在两个状态，也就是持有股票与不持有股票 n = len(prices) # dp[i][0]表示在第i天没有持有股票的最大收益,dp[i][1]表示在第i天持有股票的最大收益 dp = [[0]*2 for i in range(n+1)] dp[0][0] = 0 # 不可能持有股票的 dp[0][1] = -float('inf') for i in range(n): # 原本dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]) dp[i+1][0] = max(dp[i][0],dp[i][1]+prices[i]) # 原本dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]) dp[i+1][1] = max(dp[i][1],dp[i][0]-prices[i]) # 最大的收益就是第n天不持有股票的场景 return dp[n][0] 123.买卖股票的最佳时机III

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

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

class Solution: def maxProfit(self, prices: List[int]) -> int: # 参照买卖股票的最佳时机IV k = 2 n = len(prices) dp = [[[-float('inf')]*2 for _ in range(k+2)] for _ in range(n+1)] # 初始化 for i in range(1,k+2): dp[0][i][0] = 0 for i in range(n): for j in range(1,k+2): # j 表示已经交易了j-1次 # dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]) dp[i+1][j][0] = max(dp[i][j][0],dp[i][j][1]+prices[i]) # dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]) dp[i+1][j][1] = max(dp[i][j][1],dp[i][j-1][0]-prices[i]) return dp[n][k+1][0] 188.买卖股票的最佳时机 IV

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

思路分析：加多一个参数表示当前交易的次数

注意这个初始化

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

错误的初始化

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