Leetcode 2547. Minimum Cost to Split an Array

[Woodyiiiiiii]

这道题我一开始还傻傻地用所谓的贪心和DFS去做，显然不是正解。

难点在于要想到用DP。其实从数组大小就可以看得出来。重点是，我们要尽量遍历之前的可能，找到最小值。所以要用DP。

我一开始的想法是直接DP：

class Solution {
    public int minCost(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = k;
        for (int i = 1; i < n; ++i) {
            int len = 0;
            Map<Integer, Integer> cntMap = new HashMap<>();
            for (int j = i; j >= 0; --j) {
                cntMap.put(nums[j], cntMap.getOrDefault(nums[j], 0) + 1);
                if (cntMap.get(nums[j]) == 2) {
                    len += 2;
                } else if (cntMap.get(nums[j]) > 2) {
                    len++;
                }
                dp[i] = Math.min(dp[i], (j == 0 ? 0 : dp[j - 1]) + k + len);
            }
        }
        return dp[n - 1];
    }
}

这种方法同样AC了，但没利用好条件0 <= nums[i] < nums.length。这个条件是用来表明可以直接用数组缓存作为元素的出现次数标记。

所以观察到元素的大小，我们可以选择使用数组来计算出现次数，而不是用Map。

同时，我们可以预先处理好所有子数组的值，利用好数组长度较小的性质。使用二维数组计算好所有连续子数组的值。虽然消耗了空间，但速度明显提升。

class Solution {
    public int minCost(int[] nums, int k) {
        int n = nums.length;

        // pre-process
        int[][] cache = new int[n][n];
        for (int i = 0; i < n; ++i) {
            int[] cnt = new int[n];
            int trimmedCnt = 0;
            for (int j = i; j < n; ++j) {
                int num = nums[j];
                if (cnt[num] == 1) {
                    trimmedCnt += 2;
                } else if (cnt[num] > 1) {
                    ++trimmedCnt;
                }
                cnt[num]++;
                cache[i][j] = trimmedCnt;
            }
        }

        int[] dp = new int[n];
        for (int i = 0; i < n; ++i) {
            dp[i] = cache[0][i] + k;
            for (int j = 0; j < i; ++j) {
                dp[i] = Math.min(dp[i], dp[j] + k + cache[j + 1][i]);
            }
        }

        return dp[n - 1];
    }
}

类似题目：

• 322. Coin Change
• 410. Split Array Largest Sum (发散思维，不要思维定式)

---

• 2547. Minimum Cost to Split an Array