1,给一组股票价格变化，允许一次交易，求最大获益

思路：如是价格的最低值在最高值的前面，那最大收益就很好算了。但如不是，...

tip１:对于求最优问题，考虑动态规划。

最笨的Ｏ（n^2）方法：计算所有从后往前两两差值，最大那个就是。

是否可以减少差值的次数：

比如对于２３５，显然知道5-2＞3-2. 所以每次用当前值减当前最小值就可以了。

一遍的扫描，就足够了，但要同时保存当前最小值和当前最小收益。

best_price[i] = max(best_price[i-1],price[i]-min[i-1])

min[i] = min(min[i-1],price[i])

这两个值的更新都只与前一天有关，所以都不用保存数组。

best_price = max(best_price,　price[i]-min)

min = min(min,　price[i])

 int maxProfit(vector<int>& prices) {
       int min = INT_MAX;
       int best_price = 0;
       for (int i=0;i<prices.size();i++) {
             if (prices[i] < min) {
                 min = prices[i];
             }else  if (prices[i]-min > best_price) {
                best_price = prices[i] - min;  
             }
           
       }
       return best_price;
   }

2,给一组股票价格变化，允许多次交易，但必须是一次交易结束了，再进行下一次交易，求最大获益

在这种方式下，能赚的钱你都能赚到。

best_price += price[i] - price[i-1] >0 ? price[i] - price[i-1] : 0  i=1,...,len(price)

 int maxProfit(vector<int>&  prices) {
   int ans = 0;
   if (prices.size() == 0)
       return ans;
   for (int i=1; i<prices.size(); ++i) {
       ans += prices[i] - prices[i-1] >0 ? prices[i] - prices[i-1] :0 ;  
   }
   return ans;
}

当然，上面的方法完全看不出动态规划，这是一个贪心。

tip２：凡贪心能解决的问题，动态规划都能解决．

tip３：动态规划满足性质最优子结构的性质，通常子问题会被重复使用．

最优子结构：如果一个问题中的最有解中包含子问题的最优解。

分治法也有子问题，但是分治法在那分都行，比如快排，分完后就变成两个独立的子问题了，最后在合并这子问题。快排只有唯一解，不涉及最优解的问题。相对于分治法解决最优问题（如最近点对），子问题独立（虽然最后还要考虑中间部分的点对距离）。但是问题的最优解中不包含子问题的最优解。

tip4：贪心也满足最优子结构，同时还有满足贪心选择性。

贪心选择性：一个全局最优解可以通过局部最优（贪心）选择来达到。

拓展训练：给一组股票价格变化，允许多次交易，但必须是一次交易结束了，再进行下一次交易，求最大获益并使交易次数最少的方案。

3,给一组股票价格变化，最多允许两次交易，但必须是一次交易结束了，再进行下一次交易，求最大获益

比较直观的动态规划想法：dp[0,n] = max{dpOne[0,i] + dpOne[i+1,n] ,i =1,..,(n-2),dpOne[0,n]}

dpOne[i,j]指i到j天只进行一次交易的最大收益，问题一已经解决这个问题了。现在的问题就在原问题上加了一层遍历，时间复杂度变成了O(n^2).

可以用4的方法把时间复杂度降为O(n).

4,最多完成k次交易

再按问题三的简单想法，问题就比较麻烦了。要穷举k,还有穷举k-1的分割点。时间复杂度是不能接受的。

分两种情况，如果k>n/2,就同问题2.

如果不是，那么我们最多能进行2*k次交易，奇数项交易只能是买入，偶数项交易只能是卖出。

dp[i][j]:第i天进行第j次交易，可获得的最大利益。

dp[i][j] = max{dp[i-1][j], dp[i-1][j-1] + prices[i](j是偶数),dp[i-1][j-1] - prices[i](j是奇数)}  //每一天只有三种可能，买入，卖出，不动作。

遍历天数和2*k,时间复杂度是O(k*n).

5,一次交易完成后要等一天才能进行下一次交易，交易次数不限

相比于问题4,没有交易次数的限制，多了交易时间的限制。

状态也多了一种，冷静态。状态转移如下：

买->不动作，->卖

不动作->买，->卖

冷静态->买,->不动作

卖->冷静态

按照4题的思路：必须先判断每一天是否是冷静态，比较麻烦。

定义两个数组，buy[i],sell[i]表示第i天分布进行buy和sell交易最大利益。

sell[i] = max{buy[i-1]+prices[i],sell[i-1] + (prices[i]-prices[i-1])}// 卖出的前一天可能是买入，也可能是卖出（取消上一次的卖出）

buy[i] = max{sell[i-2]-prices[i],buy[i-1]- (prices[i]-prices[i-1])}

因为不动作和冷静态都不会对钱产生影响，所以在递归方程中并没有。