Leetcode-刷题笔记1-动态规划part08
目录
Leetcode 刷题笔记1 动态规划part08
leetcode 121 买卖股票的最佳时机
把股票问题理解为不卖和卖的两种情况，就只需要考虑两个变量即可
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if length == 0:
return 0
dp = [[0] * 2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for 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 = 0
for 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] = 0
for 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 0
length = len(prices)
dp = [0] * 5
dp[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]