动态规划 - 股票

动态规划的本质是

从子状态推出当前状态，且无后效性；需要我们合理地定义状态。

对于股票的最大利润，决定性的状态因素有三个：

第i天结束时，最多能进行k次交易，当前是否持有股票。

dp[i][k][0],dp[i][k][1]表示当前最大金额

其实，dp[i][k][0] > dp[i][k][1]，我们最终需要的是前者，但必须引入是否持有股票状态，这是由子状态推出当前状态的必要条件。

1. 学习 股票问题系列通解
2. 股票问题一共有六道题，链接如下：
   1. 买卖股票的最佳时机（求出某点右侧最大值 / 动态规划）
   2. 买卖股票的最佳时机 II（贪心 / 动态规划 k +∞，k和k-1一样）
   3. 买卖股票的最佳时机 III（ k = 2）
   4. 买卖股票的最佳时机 IV（给定k）
      1. 对于每一天需要使用不同的 k 值更新所有的最大收益，对应持有 0 份股票或 1 份股票。如果 k 超过一个临界值，最大收益就不再取决于允许的最大交易次数，而是取决于股票价格数组的长度，因此可以进行优化。那么这个临界值是什么呢？
      2. 一个有收益的交易至少需要两天（在前一天买入，在后一天卖出，前提是买入价格低于卖出价格）。如果股票价格数组的长度为 n，则有收益的交易的数量最多为 n / 2（整数除法）。因此 k 的临界值是 n / 2。如果给定的 k 不小于临界值，即 k >= n / 2，则可以将 k 扩展为正无穷，此时问题等价于情况二。
   5. 最佳买卖股票时机含冷冻期
      1. 买入时前一天未持有，且前一天不是卖出，所以前一天在休息；考虑前一天的前一天i-2应该是未持有，且可以是卖出状态。如果是非卖出状态，可以由前一天在休息获取到其值
   6. 买卖股票的最佳时机含手续费（就是在买入时加上手续费或卖出时减去手续费）
3. codetop搜索股票问题求解
   1. 注意只有买入计入交易次数就行
   2. 每天只有休息、买入、卖出三个状态