买卖股票的动态规划与贪心

动态规划与贪心介绍

动态规划类似数学中的递推关系，或者更通俗地讲数列的递推关系，根据前一项与后一项之间的关系，能够推导出后一项，而一般情况下都是根据数组前面的n-1项，推导出第n项，这很有可能就是我们要求的。这种递归也可以叫做状态转移，而数组的初始值我们也可以叫做初始状态。

而贪心思想是我们以最优的思想去考虑这个问题，即直接考虑问题的最少或者最多，有时候贪心可以由动态规划去掉空间得到。

而股票买卖这三题，主要是涉及数列中有多少个状态需要转移的问题以及动态规划转贪心的问题。

买卖股票的最好时机（一）从数组中找一个元素买入，再从它后的另一个元素卖出，求买卖的最大差值。

买卖股票的最好时机（二）是在上述基础上增加了第一次卖出后可以买第二次，卖第二次，买第三次，卖第三次……只要手里没有股票就可以买，之后前面买了股票就可以卖。

买卖股票的最好时机（三）在（一）的基础上增加最多可以买入卖出两次。

技巧

从动态规划的角度讲，到每天为止有最大收益和持股情况这两个状态，我们要通过状态的转移得到最后一天没有持股的最大收益。$dp[i][0]dp[i][0]$表示第i天不持股到该天为止的最大收益，$dp[i][1]dp[i][1]$表示第i天持股，到该天为止的最大收益，因此最基本的状态转移为：

• 初始状态： 第一天不持股，则总收益为0，$dp[0][0]=0dp[0][0]=0$；第一天持股，则总收益为买股票的花费，此时为负数，$dp[0][1]=-prices[0]dp[0][1]\; =\; -prices[0]$。
• 状态转移： 对于之后的每一天，如果当天不持股，有可能是前面的若干天中卖掉了或是还没买，因此到此为止的总收益和前一天相同，也有可能是当天才卖掉，我们选择较大的状态$dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][0]\; =\; max(dp[i\; -\; 1][0],\; dp[i\; -\; 1][1]\; +\; prices[i])$；如果当天持股，有可能是前面若干天中买了股票，当天还没卖，因此收益与前一天相同，也有可能是当天买入，此时收益为负的股价，同样是选取最大值：$dp[i][1]=max(dp[i-1][1],-prices[i])dp[i][1]\; =\; max(dp[i\; -\; 1][1],\; -prices[i])$。

不同点

• 买卖股票的最好时机（一）就只有上述状态，转移情况也同上。转化为贪心就是发现上述动态规划转移只使用了第$ii$列和第$i-1i-1$列，因此可以用变量代替。再来$dp[i][0]dp[i][0]$维护的是最大的收益，$dp[i][1]dp[i][1]$维护的是持股状态最大收益，即最小的价格，即使用两个变量维护了一个最低价格和最高价格差。

-买卖股票的最好时机（二）可以多次买入卖出，那么持股状态下的最高收益就不再是只能买入一次，而是后面的收益都可以用来买入，因此$dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])dp[i][1]\; =\; max(dp[i\; -\; 1][1],\; dp[i\; -\; 1][0]\; -\; prices[i])$，状态就在买入和卖出之间不断转移，且只能由没有持股到持股，再由持股到没有持股，如此循环。想要优化为贪心，还是类似的舍弃辅助空间：只要数组子序列是递增的，那这一段就一定有收入。

• 买卖股票的最好时机（三）增加的点在于限定了最多两次交易，则不能像（二）一样不断循环状态，因为状态有限，那我们就设置有限个状态：

  • $dp[i][0]dp[i][0]$表示到第i天为止没有买过股票的最大收益
  • $dp[i][1]dp[i][1]$表示到第i天为止买过一次股票还没有卖出的最大收益
  • $dp[i][2]dp[i][2]$表示到第i天为止买过一次也卖出过一次股票的最大收益
  • $dp[i][3]dp[i][3]$表示到第i天为止买过两次只卖出过一次股票的最大收益
  • $dp[i][4]dp[i][4]$表示到第i天为止买过两次同时也买出过两次股票的最大收益

  后续状态转移也由这五个状态之间转换：对于后续的每一天，如果当天还是状态0，则与前一天相同，没有区别；如果当天状态为1，可能是之前买过了或者当天才第一次买入，选取较大值：$dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])dp[i][1]\; =\; max(dp[i\; -\; 1][1],\; dp[i\; -\; 1][0]\; -\; prices[i])$；如果当天状态是2，那必须是在1的状态下（已经买入了一次）当天卖出第一次，或者早在之前就卖出只是还没买入第二次，选取较大值：$dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i])dp[i][2]\; =\; max(dp[i\; -\; 1][2],\; dp[i\; -\; 1][1]\; +\; prices[i])$；如果当天状态是3，那必须是在2的状态下（已经卖出了第一次）当天买入了第二次，或者早在之前就买入了第二次，只是还没卖出，选取较大值：$dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i])dp[i][3]\; =\; max(dp[i\; -\; 1][3],\; dp[i\; -\; 1][2]\; -\; prices[i])$;如果当天是状态4，那必须是在3的状态下（已经买入了第二次）当天再卖出第二次，或者早在之前就卖出了第二次，选取较大值：$dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i])dp[i][4]\; =\; max(dp[i\; -\; 1][4],\; dp[i\; -\; 1][3]\; +\; prices[i])$。

转换贪心思想还是优化辅助空间为变量，与上面相似。