北京企业网站建设方,全国好的视频制作,网络平台怎么搭建网站,公司名称大全集清单
● 123.买卖股票的最佳时机III ● 188.买卖股票的最佳时机IV
LeetCode #123 买卖股票的最佳时机 III
1. 题目
给定一个数组#xff0c;它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。 注意它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
2. 思路
dp数组含义: 最多完成两笔交易共存在五种状态 1.不交易 2. 第一次买入 3. 第一次卖出 4. 第二次买入 5. 第二次卖出 dp[i][j] 为第i天所能获取的最大利润 i 代表天数 j代表交易状态递推公式: 若i天均不操作: dp[i][0] dp[i-1][0]若i天第一次买入: dp[i][1] max(dp[i-1][1] #前一天已买入, dp[i-1][0] - prices[i] # i 天买入第i天第一次卖出: dp[i][2] max(dp[i-1][2] #前一天已卖出, dp[i-1][1] prices[i] # i 天卖出若i天第二次买入: dp[i][3] max(dp[i-1][3] #前一天已买入, dp[i-1][2] - prices[i] # i 天买入第i天第二次卖出: dp[i][4] max(dp[i-1][4] #前一天已卖出, dp[i-1][3] prices[i] # i 天卖出 初始化: dp[0][1] - prices[i] dp[0][3] - prices[i]遍历顺序: 正向遍历
3. 代码实现
class Solution:def maxProfit(self, prices: List[int]) - int:dp [[0] * 5 for _ in range(len(prices))]dp[0][1] - prices[0]dp[0][3] - prices[0]for i in range(1,len(prices)):dp[i][0] dp[i-1][0] # 不操作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 dp[-1][4]LeetCode #188 买卖股票的最佳时机 IV
1. 题目
给定一个整数数组 prices 它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
2. 思路
思路同上一题一样共存在2k1种状态 0为不操作奇数为买入偶数为卖出
3. 代码实现
class Solution:def maxProfit(self, k: int, prices: List[int]) - int:dp [[0] * ( 2 * k 1) for _ in range(len(prices))]for i in range(1, 2 * k, 2):dp[0][i] - prices[0]for i in range(1, len(prices)):for j in range(0, 2*k - 1, 2):dp[i][j1] max(dp[i-1][j1], dp[i-1][j] - prices[i])dp[i][j2] max(dp[i-1][j2], dp[i-1][j1] prices[i])return dp[-1][2*k]
