188. 买卖股票的最佳时机 IV

Problem: 188. 买卖股票的最佳时机 IV，记录官解。

做题历程

做完这题，我才发现我之前几道股票题的做法是碰巧利用了题目的特性，无法扩大到更大条件。

借着上一题的思路，我想着能否再分而治之，把k次购买分成若干个1次购买。一个想法是把数组分成若干个部分，然后对每个部分求出1次购买的值。但是这样做时间复杂度太高，是k的阶乘乘以n的数量级，而且显而易见地进行了大量的重复计算。

正确思路

我前面思路没有做出来的原因是，少利用了是否持有股票这一重要条件。把这个条件加入到动态规划条件中，并加入至多进行k次交易这个条件，题目就迎刃而解了。动态规划的转移方程可以参见代码。

由此可见遇到错误死胡同需要转变思路想想。在动态规划题目里特别是变换状态条件。

复杂度

• 时间复杂度: $O(nk)$，n为数组长度。
• 空间复杂度: $O(k)$。

Code

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        k = Math.min(n / 2, k);
        int dp[][] = new int[k + 1][2];
        for (int i = 1; i <= k; i++) {
            dp[i][1] = -prices[0];
        }
        for (int i = 1; i < n; i++){ 
            for (int j = 1; j <= k; j++) {
                dp[j][1] = Math.max(dp[j - 1][0] - prices[i], dp[j][1]);
                dp[j][0] = Math.max(dp[j][1] + prices[i], dp[j][0]);
            }
        }
        return dp[k][0];
    }
}