每日一题：LeetCode-123. 买卖股票的最佳时机 III
刷题使我快乐，满脸开心.jpg
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
示例 2：
示例 3：
示例 4：
提示：
1 <= prices.length <= 1050 <= prices[i] <= 105
思路
这道题确实有些难度，不过如果做过买卖股票的最佳时机 II，应该会有所启发，同样使用动态规划来解决问题
动态规划
使用动态规划的话，那其实就是需要看怎么全拆解问题
dp 定义
这次的交易变为了两次，那么我们的定义就不能再是买入和卖出两个情况了，而是四种：
买一次
买一次、卖一次
买两次、卖一次
买两次、卖两次
所以我们的 dp 数组定义应该如下：
buy1sell0[i]为第i天时，买一次的最大收益buy1sell1[i]为第i天时，买一次、卖一次的最大收益buy2sell1[i]为第i天时，买两次、卖一次的最大收益buy2sell2[i]为第i天时，买两次、卖两次的最大收益
状态方程
买一次的状态下，要么最大值是保持不操作的昨天的金额，要么是今天买一次后的价格的负数，也就是-price[i]选用负数来操作，是因为我们的
dp数组的定义是面向收益的最大值，而买入价格对于收益的影响是负的，所以要是用负数来表示buy1sell0[i] = max(buy1sell0[i-1], -price[i])买一次、卖一次状态下，要么是昨天的金额，要么是在买一次的最大值基础上，按今天价格出售，因为允许当日同时买入又卖出，所以不用前一天的买一次数据，即buy1sell0[i]+price[i]buy1sell1[i] = max(buy1sell1[i-1], buy1sell0[i]+price[i])买两次、卖一次状态下，有点类似买一次的状态，只是我们是在买一次、卖一次最大值的基础上操作buy2sell1[i] = max(buy2sell1[i-1], buy1sell1[i]-price[i])买两次、卖两次状态下，有点类似买一次、卖一次的状态，只是我们是在买两次、卖一次最大值的基础上操作buy2sell2[i] = max(buy2sell2[i-1], buy2sell1[i]+price[i])
此时，我们依然能够发现，其实所有的状态都只跟之前一天的数据有关系，所以
只保留之前一天的数据即可
初始化
买一次、和买两次、卖一次两个状态会有些特殊，因为他们是买入操作，此时很有可能会是一个负数，所以不能保持初始化为 0，所以需要初始化为第一天价格的负数
基本上思路就是如此了，直接上代码，
代码
版权声明: 本文为 InfoQ 作者【半亩房顶】的原创文章。
原文链接:【http://xie.infoq.cn/article/daffc019b848c485424732624】。文章转载请联系作者。
人生那么长，能写多少bug？ 2018-11-16 加入
我希望，自己永远是自己。我希望，远离bug。
评论