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