1. 題目分析

• 首先3的問題就是4中的k = 2的特例，所以我們直接考慮第四題
• 整個問題可以提煉為，當?shù)竭_第i天，我們進行至多k次交易，可以獲得最大的收益是多少。我們可以記為Global[i][k].
• 為了進行遞推(DP)，我們通常使用假設(shè)i-1的時候一定會做某事，所以我們可以設(shè)Local[i][k]為到達了第i天，我們至多進行了k次交易，且最后一次交易發(fā)生在第i天(即在第i天賣出),所獲得的最大收益。
• 當我們第i 天有賣出時 Global[i][j] = Local[i][j], 當我們第i天沒有賣出時 Global[i][j] = Global[i-1][j]， 所以 Global[i][j] = max { Local[i][j], Global[i-1][j] }.
• 對于Local[i][j]， 既然其表示第i天賣出的情況，我們可以通過這筆第i天賣出的股票是何時買入的來分情況討論。
  • 第i天當天買入，Local[i][j] = Global[i-1][j-1] + (a[i] - a[i])
  • 第i-1天買入，Local[i][j] = Global[i-1][j-1] + (a[i] - a[i-1])
  • 第i-2天買入，Local[i][j] = Global[i-2][j-1] + (a[i] - a[i-2])
  • 第i-3天買入，Local[i][j] = Global[i-3][j-1] + (a[i] - a[i-3])
  • ...
  • 第0天買入，Local[i][j] = Global[0][j-1] + (a[i] - a[0])
    最終結(jié)果應(yīng)該是取其中的最大者。但是這樣的話local又化成了global，非常難以就算，所以我們應(yīng)該考慮如何將這個式子化簡。
    首先， 對于前兩項 可以化為max{ Global[i-1][j-1] + max{ 0 , a[i] - a[i-1] } }
    對于剩下的，最后一筆交易都是在第i-2天當天或者之前買入的，考慮local[i-1][j],
    其等于下面式子取最大的那一個，
  • 1 Local[i-1][j] = Global[i-2][j-1] + (a[i-1] - a[i-1])
  • 2 Local[i-1][j] = Global[i-2][j-1] + (a[i-1] - a[i-2])
  • 3 Local[i-1][j] = Global[i-3][j-1] + (a[i-1] - a[i-3])
  • 3 Local[i-1][j] = Global[i-4][j-1] + (a[i-1] - a[i-4])
  • ...
  • 4 Local[i-1][j] = Global[0][j-1] + (a[i-1] - a[0])
    發(fā)現(xiàn)除去第一項，其他的式子中，左邊的global形式和上面剩下的式子中的global是一樣的，在考慮第一項 明顯Global[i-2][j-1] <= Global[i-1][j-1], 所以可以直接去掉，所以，只要湊一下右邊的式子就可以等價替代上面的剩下的式子了。
    local[i-1][j] -a[i-1] + a[i] = 上面的式子剩下的部分。

最終 Local[i][j] = max{ Global[i-1][j-1] + max{ 0 , a[i] - a[i-1] }, Local[i-1][j] + a[i] - a[i-1] }

2. 實現(xiàn)

//
//  main.cpp
//  leetcode
//
//  Created by YangKi on 15/11/19.
//  Copyright ? 2015年 YangKi. All rights reserved.
#include<vector>
#include<algorithm>
#include<cstdio>
#include <unordered_map>
#include <cmath>
using namespace std;

struct node
{
    int G;
    int L;
};

int getMax(int a, int b)
{
    if (a > b) return a;
    else return b;
}

class Solution {
public:
    int maxProfit2(vector<int>& prices) {
        if (prices.size() < 2)
        {
            return 0;
        }
        
        int size = (int)prices.size();
        int sum = 0;
        for (int i = 0; (i + 1) <= (size - 1); i++)
        {
            if (prices[i+1] - prices[i] > 0)
            {
                sum += (prices[i+1] - prices[i]);
            }
        }
        
        return sum;
    }
    
    int maxProfit(int k, vector<int>& prices){
        int size = (int)prices.size();
        
        if (size == 0 || size == 1)
        {
            return 0;
        }
        
       //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        if (k >= size)
        {
            return maxProfit2(prices);
        }
         //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

        node matrix[size][k+1];
        
        for (int i = 0; i< k+1; i++)
        {
            (matrix[0][i]).G = 0;
            (matrix[0][i]).L = 0;
        }
        
        for (int i = 0; i< size; i++)
        {
            (matrix[i][0]).G = 0;
            (matrix[i][0]).L = 0;
        }
        
        for (int i = 1; i < size; i++)
        {
            for (int j = 1; j < k+1; j++)
            {
                (matrix[i][j]).L = getMax((matrix[i-1][j-1]).G + getMax(0, prices[i] - prices[i-1]), (matrix[i-1][j]).L + prices[i] - prices[i-1]);
                
                (matrix[i][j]).G = getMax((matrix[i][j]).L, (matrix[i-1][j]).G);
            }
        }
        
        return (matrix[size - 1][k]).G;
    }
};

int main()
{
    
    
    Solution *s= new Solution();
    vector<int> v={1,0,1,1};
    
    return 0;
}