高端网站设计多少钱软件开发用的软件

121. 买卖股票的最佳时机

题目描述: 121. 买卖股票的最佳时机.

解法

dp

class Solution(object):def maxProfit(self, prices):if not prices:return 0dp0 = 0# 0表示不持有股票，1表示持有股票dp1 = 0-prices[0]for i in range(1,len(prices)):# 当前没有股票# 两种情况，前一天也没有，前一天的有但今天卖了dp0 = max(dp0,dp1+prices[i])# 当前有股票，昨天就有今天没卖，之前没有今天买了dp1 = max(dp1,0-prices[i])return dp0

这个题是只能买一次然后卖一次，只有一次机会。
可以使用两个变量来代替这个

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

题目描述: 122.买卖股票的最佳时机II.

解法

dp

class Solution(object):def maxProfit(self, prices):dp0 = 0dp1 = -prices[0]for i in range(len(prices)):tmp = dp0dp0 = max(dp0,dp1+prices[i])dp1 = max(dp1,tmp-prices[i])return dp0

这个是随时买随时卖。

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

题目描述: 123.买卖股票的最佳时机III.

解法

dp

class Solution(object):def maxProfit(self, prices):#0代表没有，1代表有第一支，2代表卖了第一支的没有，3代表有第二支，4代表第二支卖了。dp = [[0]*5 for _ in range(len(prices))]dp[0][1] = -prices[0]dp[0][2] = 0dp[0][3] = -prices[0]dp[0][4] = 0for i in range(1,len(prices)):dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i])dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i])dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i])return max(dp[len(prices)-1][0],dp[len(prices)-1][2],dp[len(prices)-1][4])

用多维数组表示状态。