外贸建站优化,撤销网站备案,雅安市建设局网站,洛阳专业做网站公司一、121. 买卖股票的最佳时机 题目链接#xff1a;121. 买卖股票的最佳时机 - 力扣#xff08;LeetCode#xff09; 文章讲解#xff1a;代码随想录 (programmercarl.com)——121. 买卖股票的最佳时机 视频讲解#xff1a;动态规划之 LeetCode#xff1a;121.买卖股票的最…一、121. 买卖股票的最佳时机 题目链接121. 买卖股票的最佳时机 - 力扣LeetCode 文章讲解代码随想录 (programmercarl.com)——121. 买卖股票的最佳时机 视频讲解动态规划之 LeetCode121.买卖股票的最佳时机1_哔哩哔哩_bilibili 动态规划五部曲
1. 确定 dp 数组及下标含义dp[ i ][ 0 ] 表示持有这支股票得到最大的现金dp[ i ][ 1 ] 表示不持有这支股票得到的最大的现金。由于卖出手头的钱一定比买入多所以结果为 dp[ -1 ][ 1 ]2. 确定递推公式 dp[ i ][ 0 ] max(dp[ i - 1 ][ 0 ], -price[ i ])i 天之前就持有这支股票 和 第 i 天买入这支股票的最大值 dp[ i ][ 1 ] max(dp[ i - 1 ][ 0 ] peice[ i ], dp[ i - 1][ 1 ])i - 1天之前就持有这支股票并在第 i 天卖了 和 i 天之前就不持有这支股票的最大值。3. 确定dp数组如何初始化dp[ 0 ][ 0 ] - price[ 0 ], dp[ 0 ][ 1 ] 04. 确定遍历顺序依赖前一个状态从前往后遍历其实为第二个价格5. 举例推导dp数组。
class Solution:def maxProfit(self, prices: List[int]) - int:# 创建dp数组dp [[0] * 2 for _ in range(len(prices))]# 初始化dp[0][0] -prices[0]dp[0][1] 0for i in range(1, len(prices)):dp[i][0] max(dp[i - 1][0], -prices[i])dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i])return dp[-1][1]
二、122. 买卖股票的最佳时机II 题目链接122. 买卖股票的最佳时机 II - 力扣LeetCode 文章讲解代码随想录 (programmercarl.com)——122.买卖股票的最佳时机II 视频讲解动态规划股票问题第二弹 | LeetCode122.买卖股票的最佳时机II_哔哩哔哩_bilibili Note与上一题唯一的区别是由于股票可以买卖多次dp[ i ][ 0 ] 中需要考虑 i - 1 天之前获得的利润即 dp[ i ][ 0 ] max(dp[ i - 1 ][ 0 ], dp[ i - 1][ 1 ] - price[ i ])其余部分完全一致。
class Solution:def maxProfit(self, prices: List[int]) - int:# 创建dp数组dp [[0] * 2 for _ in range(len(prices))]# 初始化dp[0][0] -prices[0]dp[0][1] 0for i in range(1, len(prices)):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]
三、123. 买卖股票的最佳时机III 题目链接123. 买卖股票的最佳时机 III - 力扣LeetCode 文章讲解代码随想录 (programmercarl.com)——123.买卖股票的最佳时机III 视频讲解动态规划股票至多买卖两次怎么求 | LeetCode123.买卖股票最佳时机III_哔哩哔哩_bilibili 动态规划五部曲
1. 确定 dp 数组及下标含义dp[ i ][ 0 ] 表示不操作dp[ i ][ 1 ] 表示第一次持有 dp[ i ][ 2 ] 表示第一次不持有dp[ i ][ 3 ] 表示第二次持有dp[ i ][ 4 ] 表示第二次不持有i 为第 i 天。由于卖出手头的钱一定比买入多且第二次卖出包含第一次卖出所以最后输出 dp[ -1 ][ 4 ]。2. 确定递推公式 dp[ i ][ 0 ] dp[ i-1 ][ 0 ] dp[ i ][ 1 ] max(dp[ i - 1 ][ 1 ], dp[ i- 1][ 0 ] - price[ i ])可以保持前一天也可以前一天不持有今天买入即第一次持有 dp[ i ][ 2 ] max(dp[ i - 1 ][ 2 ], dp[ i - 1][ 1 ] price[ i ])可以保持前一天也可以前一天第一次持有今天卖出即第一次卖出 dp[ i ][ 3 ] max(dp[ i - 1 ][ 3 ], dp[ i -1 ][ 2 ] - price[ i ])可以保持前一天也可以前一天第一次不持有今天买入即第二次持有 dp[ i ][ 4 ] max(dp[ i - 1 ][ 4 ], dp[ i -1 ][ 3 ] price[ i ])可以保持前一天也可以前一天第第二次持有今天卖出即第二次卖出3. 确定dp数组如何初始化dp[ 0 ][ 0 ] 0, dp[ 0 ][ 1 ] -price[ 0 ], dp[ 0 ][ 2 ] 0理解为同一天买卖, dp[ 0 ][ 3 ] -price[ 0 ], dp[ 0 ][ 4 ] 04. 确定遍历顺序正序遍历。5. 举例推导dp数组。
class Solution:def maxProfit(self, prices: List[int]) - int:# 创建dp数组dp [[0] * 5 for _ in range(len(prices))]# 初始化dp[0][0] 0dp[0][1] -prices[0]dp[0][2] 0dp[0][3] -prices[0]dp[0][4] 0for 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]
