使矩阵满足条件的最少操作次数

题目

输入 \(m\times n\) 的矩阵 \(grid\)，输出需要的最少操作次数，使得每列的值相等，且相邻两列的值不相等。每次操作可以将任意单元格的值修改为任意非负整数。

数据范围：\(1\leq n,m\leq 1000\)，\(0\leq grid[i][j]\leq 9\)。

思路

首先，每列的值肯定是修改为 \([0,9]\) 之间更优，因为操作次数可能更少。我们可以从前往后枚举每列修改为什么值，可以发现存在重叠子问题。定义 \(dp[i][j]\) 表示将第 \(i\) 列修改为 \(j\)，使得 \([0,i]\) 列满足条件所需的最少操作次数。有状态转移方程 \(dp[i][j]=\min{(dp[i-1][k])}+cnt_{i,j}\)，其中 \(0\leq k\leq 9\) 且 \(k\neq j\)，\(cnt_{i,j}\) 表示将第 \(i\) 列修改为 \(j\) 所需的操作次数。时间复杂度为 \(O(mn+nU^{2})\)，空间复杂度为 \(O(nU)\)，其中 \(U\) 表示 \(grid[i][j]\) 的值域大小。灵神题解提到一个优化方式，状态转移只会从前面所有列操作的最优值或者次优值转移过来，利用这个特性可以降低时间和空间复杂度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public int minimumOperations(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] cnt = new int[n][10];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cnt[j][grid[i][j]]++;
            }
        }
        
        int[][] dp = new int[n + 1][10];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    if (k != j) {
                        dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][k] + (m - cnt[i][j]));
                    }
                }
            }
        }
        
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < 10; i++) {
            ans = Math.min(ans, dp[n][i]);
        }
        return ans;
    }
}

最短路径中的边

题目

输入整数 \(n\) 和长度为 \(m\) 的数组 \(edges\)，表示包含 \(n\) 个节点和 \(m\) 条边的无向带权图（无重边和自环）。输出长度为 \(m\) 的布尔数组 \(ans\)，如果从节点 \(0\) 到节点 \(n-1\) 的所有最短路中包含 \(edges[i]\)，则 \(ans[i]=true\)。

数据范围：\(2\leq n\leq 5\times 10^{4}\)，\(1\leq m\leq\min{(5\times 10^{4},\frac{n(n-1)}{2})}\)，\(1\leq w_{i}\leq 10^{5}\)。

思路

首先使用 Dijkstra 算法求出从节点 \(0\) 到所有其他节点的最短路，然后暴力的想法是以节点 \(0\) 为起点使用 DFS 回溯来遍历图，遍历的同时存储路径上的边，当到达节点 \(n-1\) 的路径长度等于最短路时，则将该路径上的边都置为 \(true\)。回溯理论上最坏情况下的时间复杂度为 \(O(n\times n!)\)，但是可以通过力扣的测试，因为可以利用最短路的限制进行剪枝，至于能否构造出 Hack 回溯的测试用例，我不太清楚。

正确的解法是使用两次 Dijkstra 算法，分别求出从节点 \(0\) 到所有其他节点的最短路，和从节点 \(n-1\) 到所有其他节点的最短路。然后枚举每一条边，判断路径长度 \(d_{0,u}+w_{u,v}+d_{v,n-1}\) 或者 \(d_{0,v}+w_{u,v}+d_{u,n-1}\) 是否等于最短路，从而可以得出该边是否在某个最短路中。

另一种做法是只对起点使用一次 Dijkstra 算法，然后从终点反向 DFS，经过的边如果满足 \(d_{0,v}+w_{u,v}=d_{0,u}\)，则说明该边在某个最短路上。

K 个不相交子数组的最大能量值

题目

输入长度为 \(n\) 的整数数组 \(nums\) 和正奇数 \(k\)，输出从数组中选择 \(k\) 个不相交的子数组，能够得到的最大得分。\(k\) 个子数组的得分为 \(\sum_{i=1}^{k}(-1)^{i+1}\times sum[i]\times (k-i+1)\)，其中 \(sum[i]\) 表示第 \(i\) 个子数组中元素之和。

数据范围：\(1\leq n\leq 10^{4}\)，\(-10^{9}\leq nums[i]\leq 10^{9}\)，\(1\leq k\leq n\)，\(1\leq n\times k\leq 10^{6}\)。

思路

定义 \(dp[i][r]\) 表示从区间 \([0,r-1]\) 选择 \(i\) 个不相交子数组，能够得到的最大得分。对于元素 \(nums[r-1]\)，我们有选或者不选两种情况，状态转移方程如下：

初始时，对于所有 \(0\leq i\leq n\)，有 \(dp[0][i]=0\)，其他值初始化为负无穷。使用上述转移方程，时间复杂度为 \(O(kn^{2})\)。可以对其变形，将时间复杂度优化为 \(O(kn)\)，详细参见灵神的题解。小羊的题解使用的是另一种做法，似乎更简洁，但是看不太懂啊。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public long maximumStrength(int[] nums, int k) {
        int n = nums.length;
        long[] sum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }

        long[][] dp = new long[k + 1][n + 1];
        for (int i = 1; i <= k; i++) {
            Arrays.fill(dp[i], Long.MIN_VALUE);
        }

        for (int i = 0; i < k; i++) {
            long max = Long.MIN_VALUE;
            int w = (2 * (i & 1) - 1) * -1 * (k - i);
            for (int r = i; r < n - (k - i - 1); r++) {
                max = Math.max(max, dp[i][r] - sum[r] * w);
                dp[i + 1][r + 1] = Math.max(dp[i + 1][r], sum[r + 1] * w + max);
            }
        }
        return dp[k][n];
    }
}

String Bags

题目

输入字符串 \(T\) 和整数 \(N\)，表示有 \(N\) 个袋子。然后对每个袋子，输入其包含的字符串个数 \(A_{i}\)，以及 \(A_{i}\) 个字符串 \(S_{i,1},S_{i,2},\dots,S_{i,A_{i}}\)。对于每个袋子，我们只能从中选择一个字符串或者不选。输出选择袋子的最少个数，使得按照袋子的编号顺序拼接字符串，能够得到字符串 \(T\)。如果无法得到字符串 \(T\)，则输出 \(-1\)。

数据范围：\(1\leq \operatorname{len}(T)\leq 100\)，\(1\leq N\leq 100\)，\(1\leq A_{i}\leq 10\)，\(1\leq \operatorname{len}(S_{i,j})\leq 10\)。

思路

定义 \(dp[i][j]\) 表示从袋子 \([1,i]\) 中选择袋子的最少个数，使得拼接得到的字符串和 \(T\) 的前缀 \([1,j]\) 相同（下标从 \(1\) 开始）。初始状态和转移方程见代码，算是基本的动态规划，太久没做题加上原题表述有歧义，竟然没做出来。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public static void solve() {
    String t = io.next();
    int n = io.nextInt();

    int m = t.length();
    int[] dp = new int[m + 1];
    Arrays.fill(dp, m + 1);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        int z = io.nextInt();
        Set<String> set = new HashSet<>();
        for (int j = 0; j < z; j++) {
            set.add(io.next());
        }

        for (int j = m - 1; j >= 0; j--) {
            for (int k = 1; k <= 10 && k <= j + 1; k++) {
                if (set.contains(t.substring(j - k + 1, j + 1))) {
                    dp[j + 1] = Math.min(dp[j + 1], dp[j + 1 - k] + 1);
                }
            }
        }
    }
    io.println(dp[m] == m + 1 ? -1 : dp[m]);
}