Algorithm之动态规划之最佳买股票时机

动态规划（DP: Dynamic Programming）

一、基本思想与策略

基本思想与分治法类似，也是将待求解的问题
    - 分解为若干个子问题（阶段）
    - 按顺序求解子问题，
    - 前一个（或前有限个，一般不超过三个）子问题的解，为后一子问题的求解提供了有用的信息。
    - 在求解子问题时，需要求得各种可能的解。这些解是累计关系，是当前子问题的最终解。
    - 依次解决各子问题，最后一个子问题的解就是初始问题的解。

动态规划的子问题是可以用来判定结果的最短子问题，或是前后两个，或是前后三个，总之是有限个。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，
可将子问题及其输出保存在一个二维数组中。

与分治法最大的差别是：
适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的，
即下一个子问题的求解是建立在上一个（几个）子问题的解的基础上进行求解。


二、动态规划过程

每次决策需要依赖于以前的状态，随即又产生新的状态。
每步都选择最优状态，但是其它状态也需要保留，以便为后面的决策提供依据。
一个决策序列就是在变化的状态中产生出来的，所以这种多阶段最优化决策解决问题的过程就称为动态规划。


三、例子：最佳买股票时机（三种情况）

1、Best Time to Buy and Sell Stock -- LeetCode
http://blog.csdn.net/linhuanmars/article/details/23162793

求进行一次交易能得到的最大利润。
用“局部最优和全局最优解法”。
思路是维护两个变量，一个是到目前为止最好的交易，另一个是今天买明天卖的最佳交易。
这样一次扫描就可以得到结果，时间复杂度是O(n)。而空间只需要两个变量，即O(1)。

public int maxProfit(int[] prices) {  
    if(prices==null || prices.length==0) return 0;  
    int local = 0;  
    int global = 0;  
    for(int i=0;i<prices.length-1;i++){
        local = Math.max(local+prices[i+1]-prices[i],0);  
        global = Math.max(local, global);  
    }  
    return global;  
}

这种题目的解法非常经典，不过是比较简单的动态规划。


2、Best Time to Buy and Sell Stock II -- LeetCode
http://blog.csdn.net/linhuanmars/article/details/23164149

可以交易任意次数。
只要对每次两天差价大于0的都进行交易，就可以得到最大利润。
因此算法其实就是累加所有大于0的差价既可以了。

public int maxProfit(int[] prices) {  
    if(prices == null || prices.length==0) return 0;
    int res = 0;  
    for(int i=0;i<prices.length-1;i++){    
        int diff = prices[i+1]-prices[i];  
        if(diff>0)  
            res += diff;  
    }  
    return res;  
}  

3、Best Time to Buy and Sell Stock III -- LeetCode
http://blog.csdn.net/linhuanmars/article/details/23236995

最多可以进行K次交易。
还是使用“局部最优和全局最优解法”。
对于天数需要一次扫描，而每次要对交易次数进行递推式求解，所以时间复杂度是O(n*k)。

下面是 K = 2 的情况：

public int maxProfit(int[] prices){
    if(prices==null || prices.length==0) return 0;
    int[] local = new int[3];
    int[] global = new int[3];
    for(int i=0;i<prices.length-1;i++){
        int diff = prices[i+1]-prices[i];
        for(int j=2;j>=1;j--){
            local[j] = Math.max(global[j-1]+(diff>0?diff:0), local[j]+diff);
            global[j] = Math.max(local[j],global[j]);
        }
    }
    return global[2];
}

完善版本：

/*
* j -- max # of transactions; i --- # of days;
*  local[i][j] -- profit achieved when selling at last day;
*  global[i][j] --- profit achieved at all situations;
*  transition equation:
*       local[i][j] =  max(local[i - 1][j], global[i - 1][j - 1]) + diff;
*      (merge with previous transactions or NOT)
*      global[i][j] = max(local[i][j], global[i - 1][j]);
*/
public class SolutionIV {
    public int maxProfit(int k, int[] prices) {
            int N = prices.length;
            if (k >= N)
                    return simpleMaxProfit(prices);
        int[] local = new int[k + 1], global = new int[k + 1];
        int[] prevLocal = new int[k + 1], prevGlobal = new int[k + 1];
        for (int i = 1; i < N; ++i) {
                prevLocal = local; prevGlobal = global;
                local = new int[k + 1]; global = new int[k + 1];
                int diff = prices[i] - prices[i - 1];
                for (int j = 1; j <= k; ++j) {
                        local[j] = Math.max(prevGlobal[j - 1], prevLocal[j]) + diff;
                        global[j] = Math.max(local[j], prevGlobal[j]);
                }
        }
        return global[k];
    }
    int simpleMaxProfit(int[] prices) {
            int N = prices.length;
            if (N <= 1)
                    return 0;
            int sum = 0;
            for (int i = 1; i < N; i++) {
                    int diff = prices[i] - prices[i - 1];
                    if (diff > 0)
                            sum += diff;
            }
            return sum;
    }
    public static void main(String[] args) {
        SolutionIV sol = new SolutionIV();
        int[] nums = {4, 6, 1, 1, 4, 2, 5};
        System.out.println(sol.maxProfit(2, nums));
    }
}

四、例子：买股票的最佳时机

package solution;

import org.junit.Test;

public class BestTimetoBuyAndSellStockwithCooldown {
    
    
// 最佳买股票时间有多种玩法和限制。
// 本例只举其一种。
/*
LeetCode : 
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
309. Best Time to Buy and Sell Stock with Cooldown
 * 
Say you have an array for which the ith element is the price of a given stock 
on day i.

Design an algorithm to find the maximum profit. You may complete as many 
transactions as you like (ie, buy one and sell one share of the stock multiple 
times) with the following restrictions:

    - You may not engage in multiple transactions at the same time 
      (ie, you must sell the stock before you buy again).
      
    - After you sell your stock, you cannot buy stock on next day. 
      (ie, cooldown 1 day)
    
Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

 */

    @Test
    public void testBuyandSell(){
        int[] prices = new int[] {1, 2, 7, 0, 2, 7, 100};
        System.out.println(maxProfit(prices));
    }
    
/*
 * 分析：    
 *------------------------------------------------------------------------------
 *
 *     对于每天来讲：只会出现在这三种状态之中：buy, sell, rest
 *        
 * buy[i] means before day i what is the maxProfit for any sequence end with buy.
 *        计算今天状态为 buy 时的最好收益：
 *        buy[i]  = max(rest[i-1]-price, buy[i-1])
 *        买入的状态 =  max（昨天冻结今天买，昨天已买入） 
 *
 * sell[i] means before day i what is the maxProfit for any sequence end with sell.
 *        记算今天状态为 sell 时的最好收益：
 *        sell[i] = max(buy[i-1]+price, sell[i-1])
 *        卖出的状态 = max（昨天为买今天卖出，昨天已卖出）
 *        
 * rest[i] means before day i what is the maxProfit for any sequence end with rest.
 *        记算今天状态为 rest 时的最好收益：
 *        rest[i] = sell[i-1]
 * 
 * -------------------------------------------------------------------------------------
   
    The series of problems are typical dp. The key for dp is to find the variables 
    to represent the states and deduce the transition function.

    Of course one may come up with a O(1) space solution directly, 
    but I think it is better to be generous when you think and be greedy when you 
    implement.
    
    The natural states for this problem is the 3 possible transactions : 
    buy, sell, rest. 
    
    Here rest means no transaction on that day (aka cooldown).    
    Then the transaction sequences can end with any of these three states.    
    For each of them we make an array, buy[n], sell[n] and rest[n].
    
        buy[i] 
        means before day i what is the maxProfit for any sequence end with buy.
    
        sell[i] 
        means before day i what is the maxProfit for any sequence end with sell.
    
        rest[i] 
        means before day i what is the maxProfit for any sequence end with rest.
    
    Then we want to deduce the transition functions for buy sell and rest. 
    By definition we have:
    
    buy[i]  = max(rest[i-1]-price, buy[i-1]) 
    sell[i] = max(buy[i-1]+price, sell[i-1])
    rest[i] = max(sell[i-1], buy[i-1], rest[i-1])
    
    Where price is the price of day i. All of these are very straightforward. 
    They simply represents :
    
    (1) We have to `rest` before we `buy` and 
    (2) we have to `buy` before we `sell`
    One tricky point is how do you make sure you sell before you buy, since
    from the equations it seems that [buy, rest, buy] is entirely possible.
    
    Well, the answer lies within the fact that buy[i] <= rest[i] which means 
    rest[i] = max(sell[i-1], rest[i-1]). That made sure [buy, rest, buy] is 
    never occurred.
    
    A further observation is that and rest[i] <= sell[i] is also true 
    therefore:
    
    rest[i] = sell[i-1]
    
    Substitute this in to buy[i] we now have 2 functions instead of 3:
    
    buy[i] = max(sell[i-2]-price, buy[i-1])
    sell[i] = max(buy[i-1]+price, sell[i-1])
    
    This is better than 3, but we can do even better
    
    Since states of day i relies only on i-1 and i-2 we can reduce 
    the O(n) space to O(1). 
  
     */

    private int maxProfit(int[] prices) {
        int sell = 0, prev_sell = 0, buy = Integer.MIN_VALUE, prev_buy;
        for (int price : prices) {
            prev_buy = buy;
            buy = Math.max(prev_sell - price, prev_buy);
            prev_sell = sell;
            sell = Math.max(prev_buy + price, prev_sell);
        }
        return sell;
    }
    

}

引用：
https://zh.wikipedia.org/zh-tw/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92

http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

五大常用算法之二：动态规划算法
http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html












-