Leetcode 刷题笔记1 动态规划part08

leetcode 121 买卖股票的最佳时机

把股票问题理解为不卖和卖的两种情况，就只需要考虑两个变量即可

class Solution:def maxProfit(self, prices: List[int]) -> int:length = len(prices)if length == 0:return 0dp = [[0] * 2 for _ in range(length)]dp[0][0] = -prices[0]dp[0][1] = 0for i in range(1, length):dp[i][0] = max(dp[i - 1][0], -prices[i])dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])return dp[-1][1]

leetcode 122 买卖股票的最佳时机 ||

class Solution:def maxProfit(self, prices: List[int]) -> int:result = 0for i in range(1, len(prices)):profit = prices[i] - prices[i - 1]result += max(profit, 0)return result

上题代码改编：

class Solution:def maxProfit(self, prices: List[int]) -> int:length = len(prices)dp = [[0] * 2 for _ in range(length)]dp[0][0] = -prices[0]dp[0][1] = 0for i in range(1, length):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][1]

leetcode 123 买卖股票的最佳时机 |||

class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices) == 0:return 0length = len(prices)dp = [0] * 5dp[1] = dp[3] = float('-inf')for i in range(length):dp[1] = max(dp[1], dp[0] - prices[i])dp[2] = max(dp[2], dp[1] + prices[i])dp[3] = max(dp[3], dp[2] - prices[i])dp[4] = max(dp[4], dp[3] + prices[i])return dp[4]