今日专题 动态规划 股票买卖
今日总结:动态规划得好好想一想需要什么状态,状态其实是用来描述子问题的
121. 买卖股票的最佳时机
解法一:动态规划
class Solution:def maxProfit(self, prices: List[int]) -> int:#dp[i][j] 表示当前拥有的钱 i表示天数,j表示第i天是否还持有这只股票 j取值0或1size=len(prices)dp=[[0]*2 for _ in range(size)]dp[0][1]=-prices[0]for i in range(1,size):dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1]=max(dp[i-1][1],-prices[i])return dp[-1][0]
解法二:贪心解法
class Solution:def maxProfit(self, prices: List[int]) -> int:res=0min_price=prices[0]for p in prices:res=max(res,p-min_price)min_price=min(p,min_price)return res
122. 买卖股票的最佳时机 II
解法一:动态规划解法
class Solution:def maxProfit(self, prices: List[int]) -> int:#dp[i][j] 表示当前拥有的钱 i表示天数,j表示第i天是否还持有这只股票 j取值0或1size=len(prices)dp=[[0]*2 for _ in range(size)]dp[0][1]=-prices[0]for i in range(1,size):dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])return dp[-1][0]
解法二:贪心解法
class Solution:def maxProfit(self, prices: List[int]) -> int:#相邻的两天,如果后一天比前一天高,则可以在前一天买后一天卖res=0temp=10**4+1for price in prices:if price-temp>0:res+=price-temptemp=pricereturn res
123. 买卖股票的最佳时机 III
class Solution:def maxProfit(self, prices: List[int]) -> int:# dp[i][j][k] i表示天数 j表示是否持有股票 k表示完成交易数size = len(prices)dp = [[[0 for _ in range(3)] for _ in range(2)] for _ in range(size)]dp[0][1][0] = -prices[0]dp[0][1][1] = -prices[0]for i in range(1, size):# 不持有可能是前一天不持有(交易0/1/2)或者前一天持有(0/1)dp[i][0][2] = max(dp[i - 1][0][2], dp[i - 1][1][1] + prices[i])dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][1][0] + prices[i])dp[i][0][0] = dp[i - 1][0][0]# 当天持有 可能是当天买的,前一天(0/1),或者前一天就有的(0/1)dp[i][1][0] = max(dp[i - 1][1][0], -prices[i])dp[i][1][1] = max(dp[i - 1][0][1] - prices[i], dp[i - 1][1][1])return max(dp[-1][0][0], dp[-1][0][1], dp[-1][0][2])