LC-2547.拆分数组的最小代价

题目描述

leetcode 困难题

给你一个整数数组 nums 和一个整数 k 。

将数组拆分成一些非空子数组。拆分的 代价 是每个子数组中的 重要性 之和。

令 trimmed(subarray) 作为子数组的一个特征，其中所有仅出现一次的数字将会被移除。

例如，trimmed([3,1,2,4,3,4]) = [3,4,3,4] 。
子数组的 重要性 定义为 k + trimmed(subarray).length 。

例如，如果一个子数组是 [1,2,3,3,3,4,4] ，trimmed([1,2,3,3,3,4,4]) = [3,3,3,4,4] 。这个子数组的重要性就是 k + 5 。
找出并返回拆分 nums 的所有可行方案中的最小代价。

子数组 是数组的一个连续 非空 元素序列。

示例1：

输入：nums = [1,2,1,2,1,3,3], k = 2
输出：8
解释：将 nums 拆分成两个子数组：[1,2], [1,2,1,3,3]
[1,2] 的重要性是 2 + (0) = 2 。
[1,2,1,3,3] 的重要性是 2 + (2 + 2) = 6 。
拆分的代价是 2 + 6 = 8 ，可以证明这是所有可行的拆分方案中的最小代价。

提示1：

1 <= nums.length <= 1000
0 <= nums[i] < nums.length
1 <= k <= 10^9

动态规划

定义 $dp[i]$ 表示拆分数组 $[0…i - 1]$ 部分的最小代价，$dp[0]$ 为 $0$ ，$dp[n]$ 为答案。

对于每个 $dp[i]$ ，我们倒序枚举最后一个切分点所有的可能，即 $[i - 2…0]$ ，并同时维护以当前作为最后一个划分点时最后一个数组的重要性 $importance$，那么就有：

$$
\begin{align}
&dp(i) = max(dp[j] + imporitance)　　　　　　　　　　　　　　　　　　0 <= j <= i - 1\\
\\
\end{align}
$$

class Solution {
    public int minCost(int[] nums, int k) {
        int n = nums.length;
        long[] dp = new long[n + 1];
        for(int i = 1; i < n + 1; i++){
            dp[i] = Integer.MAX_VALUE;
            Map<Integer, Integer> cnt = new HashMap<>();
            int importance = k;
            for(int j = i - 1; j >= 0; j--){
                int newV = cnt.merge(nums[j], 1, (old, defaultV) -> ++old);
                importance += newV == 2 ? 2 : 0;
                importance += newV > 2 ? 1 : 0;
                dp[i] = Math.min(dp[i], dp[j] + importance);
            }
        }
        return (int)dp[n];
    }
}

线段树

考虑通过线段树优化 倒序枚举最后一个切分点所有可能 这一过程，实际上即区间更新、区间查询最小值的线段树。

class Solution {
    public int minCost(int[] nums, int k) {
        int n = nums.length;
        long[] dp = new long[n + 1];
        SegTree segTree = new SegTree(dp);
        int[] last = new int[n], last2 = new int[n];
        long ans = 0;
        for(int i = 1; i < n + 1; i++){
           int x = nums[i - 1];
           segTree.update(i, i, ans, 1, n, 1); // 更新 dp[i - 1]
           segTree.update(last[x] + 1, i, -1, 1, n, 1);
           if(last[x] > 0){
               segTree.update(last2[x] + 1, last[x], 1, 1, n, 1);
           }
           ans = k + segTree.query(1, i, 1, n, 1);
           last2[x] = last[x];
           last[x] = i;
        }
        return (int)ans + n;
    }
}

class SegTree {
    long[] arr;
    int[] lazyTag;

    public SegTree(long[] org) {
        this.arr = new long[org.length * 4];
        this.lazyTag = new int[org.length * 4];
    }

    private void do_(int o, long v) {
        arr[o] += v;
        lazyTag[o] += v;
    }

    private void spread(int o) {
        int v = lazyTag[o];
        if (v != 0) {
            do_(o * 2, v);
            do_(o * 2 + 1, v);
            lazyTag[o] = 0;
        }
    }

    public void update(int l, int r, long c, int s, int t, int p){
        if (l <= s && r >= t) {
            do_(p, c);
            return;
        }
        int mid = s + (t - s >> 1);
        spread(p);
        if (l <= mid) {
            update(l, r, c, s, mid, p * 2);
        }
        if (r >= mid + 1) {
            update(l, r, c, mid + 1, t, p * 2 + 1);
        }
        arr[p] = Math.min(arr[p * 2], arr[p * 2 + 1]);
    }

    public long query(int l, int r, int s, int t, int p){
        if (l <= s && r >= t) {
            return arr[p];
        }
        int mid = s + (t - s >> 1);
        spread(p);
        long min = Long.MAX_VALUE;
        if (l <= mid) {
            min = Math.min(min, query(l, r, s, mid, p * 2));
        }
        if (r >= mid + 1) {
            min = Math.min(min, query(l, r, mid + 1, t, p * 2 + 1));
        }
        return min;
    }

}