1. 题目分析

• 首先3的问题就是4中的k = 2的特例，所以我们直接考虑第四题
• 整个问题可以提炼为，当到达第i天，我们进行至多k次交易，可以获得最大的收益是多少。我们可以记为Global[i][k].
• 为了进行递推(DP)，我们通常使用假设i-1的时候一定会做某事，所以我们可以设Local[i][k]为到达了第i天，我们至多进行了k次交易，且最后一次交易发生在第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])
    最终结果应该是取其中的最大者。但是这样的话local又化成了global，非常难以就算，所以我们应该考虑如何将这个式子化简。
    首先， 对于前两项 可以化为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])
    发现除去第一项，其他的式子中，左边的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. 实现

//
//  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;
}