Leetcode 123. Best Time to Buy and Sell Stock III / IV / Minimum White Tiles

[Woodyiiiiiii]

123. Best Time to Buy and Sell Stock III / IV

这两道题跟下面周赛的题目类似，也是DP的做法，可以扩展到k维度。

类似题目：

• 123. Best Time to Buy and Sell Stock III
• 188. Best Time to Buy and Sell Stock IV
• 2209. Minimum White Tiles After Covering With Carpets
• https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/solutions/2834741/c-easy-solution/
• https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/solutions/135704/detail-explanation-of-dp-solution/

我的思路是：对于[0,i]，我知道[0, j] (j<=i)的最大segment，那如何去求[j, i]的segment呢？所以卡在了这里。

下面是最好理解的做法，延伸了我的思考，不妨计算[j,i]时改成计算i=n-1时的最大segment：

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] suf = new int[n];
        int max = prices[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            suf[i] = Math.max(suf[i + 1], max - prices[i]);
            max = Math.max(max, prices[i]);
        }
        int min = prices[0], ans = 0;
        for (int i = 1; i < n; ++i) {
            ans = Math.max(ans, prices[i] - min + (i + 1 < n ? suf[i + 1] : 0));
            min = Math.min(min, prices[i]);
        }
        return ans;
    }
}

那如果严谨点呢？就要建造二维dp数组dp[k + 1][n]了。其中dp[i][j]表示分成i个segment下的[0,j]的最大segment。容易得到递推方程dp[k, i] = max(dp[k, i-1], prices[i] - prices[j] + dp[k-1, j-1]), j=[0..i-1]。建立k+1宽度的数组是因为考虑到k=1的情况。

容易得到如下写法：

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

为什么是prices[j] - dp[k - 1][j - 1]呢？因为最后要计算prices[i] - min，所以要min最小。

但显然O(k * n^2)是超时了，可以发现min被重复计算了，同样用DP的思想可以继续简化：

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

总结：
非常有技巧的DP思维；k维度的递推公式计算及简化。

---

2555. Maximize Win From Two Segments

先看条件：

1. 数组内元素代表位置，并且按升序排序
2. 选2个部分，每个部分都是k长度
3. 求最大数目的prize

这道题是双周赛第三题，我想了很久没做出来，感觉不应该呀：我的思路是用二分法，但无法写出移动函数，因为主要矛盾还是条件2，如何选出2个k长度。

那么需要转换思维了，从题目条件出发，想到合适的解决问题的模型。首先k长度的segment，我们可以通过滑动窗口找到k范围内的最大prize数目；然后如何选2个segment使之和最大？或者说k个segment最大？那就要用到动态规划了。滑动窗口到i位置，找到[i-k,i]范围内最大后，使用之前积累的dp得到[0,i-k]范围最大prize数目的segment，更新答案，最后更新dp。

同理，如果题目是k个segment，也是同样的做法，dp扩展成二维数组，长度为k。

总结：

1. 不能惯性思维，要从条件出发，想到相应方法/结构去解决
2. 锻炼逻辑思维，发散思维，加快思考速度，还有及时转换思路的能力
3. 刷题关键在于思维

class Solution {
    public int maximizeWin(int[] prizePositions, int k) {
        int l = 0, r = 0;
        int ans = 0;
        int[] dp = new int[prizePositions.length + 1];
        while (r < prizePositions.length) {
            while (prizePositions[l] < prizePositions[r] - k && l < r) {
                ++l;
            }
            dp[r + 1] = Math.max(dp[r], r - l + 1);
            ans = Math.max(ans, r - l + 1 + dp[l]);
            ++r;
        }
        return ans;
    }
}

---

• 2555. Maximize Win From Two Segments
• lee & 类似题目