Leetcode-188-Best Time to Buy an

这道题是买卖股票问题的终极版，即给定一个数组表示各天的股价，给定k表示最多可以交易的次数（一次交易定义为buy+sell），各次交易之间不能交叉，问最大收益是多少。

这题可以使用动态规划求解。记为在天进行至多次次交易可以得到的最大收益。不难写出转移方程：

其意义为，在第天我们有两个选择：

1、什么都不做（或买入）。此时收益与第天相同，为。

2、卖出股票。若想在第天卖出股票，须在第天（）买入股票，最大收益是。即在天进行至多次交易的最大收益加上第天卖出股票取得的收益。

按照上述过程进行计算，算法复杂度为，并不是非常理想。能否优化计算过程呢？将写成如下形式：。

从而我们可以把循环写成如下形式：

DP loop:

for i : 1 -> k
    maxTemp = -prices[0];
    for j : 1 -> n-1
        dp[i][j] = max(dp[i][j-1], prices[j]+maxTemp);
        maxTemp = max(maxTemp, dp[i-1][j-1]-prices[j]);
return dp[k][n-1];

从而我们的算法复杂度降到了，完整代码如下：

class Solution 
{
public:
    int maxProfit(int k, vector<int> &prices)
    {
        int n=prices.size();
        if (n<2) return 0;
        if (k>n/2)
        {
            int ans=0;
            for (int i=1;i<n;i++)
                ans+=max(prices[i]-prices[i-1],0);
            return ans;
        }
        vector<vector<int>> dp(k+1,vector<int>(n,0));
        int maxTemp;
        for(int i=1;i<=k;i++)
        {
            maxTemp=-prices[0];
            for(int j=1;j<n;j++)
            {
                dp[i][j]=max(dp[i][j-1],prices[j]+maxTemp);
                maxTemp=max(maxTemp,dp[i-1][j-1]-prices[j]);
            }
        }
        return dp[k][n-1];
    }
};