此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解.
目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容).
关于本专栏所有题目的目录链接, 刷算法题目的顺序/注意点/技巧, 以及思维导图源文件问题请点击此链接.
想进大厂, 刷算法是必不可少的, 欢迎和博主一起打卡刷力扣算法, 博主同步更新了算法视频讲解 和 其他文章/导图讲解, 更易于理解, 欢迎来看!
关注博主获得题解更新的最新消息!!!
本题最难的地方就在于 dp数组的构建了, 因为它不像前面讲过的两道股票问题那样, dp数组只需要用两种状态就可以表示了: 当天持有/不持有股票. 本题由于加了 最多买卖两次 的条件, 使问题一下子就变得复杂了, 用之前的两种状态并不能体现 最多买卖两次 的限制, 所以我们需要重新设计dp数组.
用上图中的五种状态就可以完美地体现出 最多买卖两次 的限制, 然后经过分析可以看出第一种状态利润为0, 对结果没什么影响, 所以我们最终只要定义剩下的4个状态即可. 定义dp数组的名称还是一贯地采用比较容易识别的名称, 这比那些用到二维dp数组, 甚至有些题解用到了三维dp数组要好多了.
定义出了dp数组之后, 按照前面两题的经验, 递推公式就没太大难度了, 还是每种状态都由两种情况组合而来, 最终取最大值:
本题的初始化也有一定难度, 毕竟dp数组实在太多了.
先来明确下题目中的隐含条件: 无论题目中是否允许「在同一天买入并且卖出」这一操作, 最终的答案都不会受到影响, 这是因为这一操作带来的收益为零, 所以为了方便初始化, 这里默认是可以的. 于是就有了下面的初始化过程:
如果题目不允许的话, 那初始化就会稍微麻烦一些了, 比如sell1[i]就只能在第二天进行sell1[1]的初始化了, 同理: buy2[i]在第三天进行buy2[2]的初始化, sell2[i]在第四天进行sell2[3]的初始化, 这就是能否「在同一天买入并且卖出」的不同之处.
在动态规划结束后,由于我们可以进行不超过两笔交易,因此最终的答案在0,sell1[i],sell2[i]中, 且为三者中的最大值, 由于在边界条件中sell1[i],sell2[i]的值已经为0, 并且在状态转移的过程中我们维护的是最大值, 因此sell1[i],sell2[i]最终一定大于等于0.
同时, 如果最优的情况对应的是恰好一笔交易, 那么它也会因为我们在转移时允许在同一天买入并且卖出这一宽松的条件, 从sell1[i]转移至sell2[i], 可以理解假如最优是 sell1[i] 的话, 可以当天再做一次买卖, 也就是完成两次交易, 所以无论如何都可以是 sell2[i] 最优.
代码在空间优化上和我们之前说过的直接将数组用变量来替换就可以了, 但是它在理解上还是有一定难度的.
例如在计算sell1[i]时, 我们直接使用buy1[i]而不是buy1[i-1]进行转移。buy1[i]比 buy[i-1]多考虑的是在第i天买入股票的情况, 而转移到sell1[i]时, 考虑的是在第i天卖出股票的情况, 这样在同一天买入并且卖出收益为零, 不会对答案产生影响, 所以我们才能这样进行优化.
## 未进行空间优化class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) buy1 = [0] * n sell1 = [0] * n buy2 = [0] * n sell2 = [0] * n buy1[0] = buy2[0] = -prices[0] sell1[0] = sell2[0] = 0 for i in range(1, n): buy1[i] = max(buy1[i-1], -prices[i]) sell1[i] = max(sell1[i-1], buy1[i-1] + prices[i]) buy2[i] = max(buy2[i-1], sell1[i-1] - prices[i]) sell2[i] = max(sell2[i-1], buy2[i-1] + prices[i]) return sell2[-1]## 空间优化class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) buy1 = buy2 = -prices[0] sell1 = sell2 = 0 for i in range(1, n): buy1 = max(buy1, -prices[i]) sell1 = max(sell1, buy1 + prices[i]) buy2 = max(buy2, sell1 - prices[i]) sell2 = max(sell2, buy2 + prices[i]) return sell2//未进行空间优化class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[] buy1 = new int[n]; int[] sell1 = new int[n]; int[] buy2 = new int[n]; int[] sell2 = new int[n]; buy1[0] = -prices[0]; sell1[0] = 0; buy2[0] = -prices[0]; sell2[0] = 0; for (int i = 1; i < n; ++i) { buy1[i] = Math.max(buy1[i-1], -prices[i]); sell1[i] = Math.max(sell1[i-1], buy1[i-1] + prices[i]); buy2[i] = Math.max(buy2[i-1], sell1[i-1] - prices[i]); sell2[i] = Math.max(sell2[i-1], buy2[i-1] + prices[i]); } return sell2[n-1]; }}我的更多精彩文章链接, 欢迎查看
各种电脑/软件/生活/音乐/动漫/电影技巧汇总(你肯定能够找到你需要的使用技巧)
力扣算法刷题 根据思维导图整理笔记快速记忆算法重点内容(欢迎和博主一起打卡刷题哦)
计算机专业知识 思维导图整理
最值得收藏的 Python 全部知识点思维导图整理, 附带常用代码/方法/库/数据结构/常见错误/经典思想(持续更新中)
最值得收藏的 C++ 全部知识点思维导图整理(清华大学郑莉版), 东南大学软件工程初试906科目
最值得收藏的 计算机网络 全部知识点思维导图整理(王道考研), 附带经典5层结构中英对照和框架简介
最值得收藏的 算法分析与设计 全部知识点思维导图整理(北大慕课课程)
最值得收藏的 数据结构 全部知识点思维导图整理(王道考研), 附带经典题型整理
最值得收藏的 人工智能导论 全部知识点思维导图整理(王万良慕课课程)
最值得收藏的 数值分析 全部知识点思维导图整理(东北大学慕课课程)
最值得收藏的 数字图像处理 全部知识点思维导图整理(武汉大学慕课课程)
红黑树 一张导图解决红黑树全部插入和删除问题 包含详细操作原理 情况对比
各种常见排序算法的时间/空间复杂度 是否稳定 算法选取的情况 改进 思维导图整理
人工智能课件 算法分析课件 Python课件 数值分析课件 机器学习课件 图像处理课件
考研相关科目 知识点 思维导图整理
考研经验–东南大学软件学院软件工程(这些基础课和专业课的各种坑和复习技巧你应该知道)
东南大学 软件工程 906 数据结构 C++ 历年真题 思维导图整理
最值得收藏的 考研高等数学 全部知识点思维导图整理(张宇, 汤家凤), 附做题技巧/易错点/知识点整理
最值得收藏的 考研线性代数 全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理
考研思修 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研近代史 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研马原 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研数学课程笔记 考研英语课程笔记 考研英语单词词根词缀记忆 考研政治课程笔记
Python相关技术 知识点 思维导图整理
Numpy常见用法全部OneNote笔记 全部笔记思维导图整理
Pandas常见用法全部OneNote笔记 全部笔记思维导图整理
Matplotlib常见用法全部OneNote笔记 全部笔记思维导图整理
PyTorch常见用法全部OneNote笔记 全部笔记思维导图整理
Scikit-Learn常见用法全部OneNote笔记 全部笔记思维导图整理
Java相关技术/ssm框架全部笔记
科技相关 小米手机
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/122206.html
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
摘要：此专栏文章是对力扣上算法题目各种方法的总结和归纳整理出最重要的思路和知识重点并以思维导图形式呈现当然也会加上我对导图的详解目的是为了更方便快捷的记忆和回忆算法重点不用每次都重复看题解毕竟算法不是做了一遍就能完全记住的所 ...
摘要：此专栏文章是对力扣上算法题目各种方法的总结和归纳整理出最重要的思路和知识重点并以思维导图形式呈现当然也会加上我对导图的详解目的是为了更方便快捷的记忆和回忆算法重点不用每次都重复看题解毕竟算法不是做了一遍就能完全记住的所 ...
阅读 2712·2021-11-11 10:58
阅读 1660·2021-10-11 10:59
阅读 3397·2019-08-29 16:23
阅读 2224·2019-08-29 11:11
阅读 2696·2019-08-28 17:59
阅读 3638·2019-08-27 10:56
阅读 1889·2019-08-23 18:37
阅读 2969·2019-08-23 16:53
