【LeetCode第366场周赛】8028. 执行操作使两个字符串相等 | 线性DP | 中等

题目内容

原题链接

给定两个长度均为 $n$ 的 $01$ 字符串 $s1$ 和 $s2$，以及一个正整数 $x$ ，每次操作有两种选择：

• 选择两个下标 $i$ 和 $j$ ，同时反转 $s1[i]$ 和 $s1[j]$ ，代价为 $x$
• 选择一个下标 $i$ 满足 $i+1<n$ ，同时反转 $s1[i]$ 和 $s1[i+1]$ ，代价为 $1$

问使得 $s1$ 变为 $s2$ 的最小代价，如果不能使得 $s1$ 变为 $s2$ ，返回 $-1$

数据范围

• $1\le n,x\le 500$
• $s1$ 和 $s2$ 均只包含字符 '0' 和 '1'

题解

这里 $s1$ 和 $s2$ 中不同的数位的数量必须为偶数，否则 $s1$ 必然无法变为 $s2$

考虑 $f[i][0/1]$ 表示将 $s1$ 的前 $i$ 个字符反转使得 $s1[0:i]=s2[0:i]$ 的最小代价。

其中 $f[i][1]$ 表示选择了若干次操作 $1$ ，最后一次操作 $1$ 只对下标 $i$ 使用了，但是未对下标 $j$ 使用，就是说我有且仅有存在一次操作 $1$ 满足只选择了下标 $i$ ，还未确定下标 $j$ 。

状态转移：

// 第 i 位选择操作 2
f[i][0] = min(f[i][0], f[i - 2][0] + p[i - 1] - p[i - 2]);
f[i][1] = min(f[i][1], f[i - 2][1] + p[i - 1] - p[i - 2]);
// 第 i 位选择操作 1
f[i][0] = min(f[i][0], f[i - 1][1]);
f[i][1] = min(f[i][1], f[i - 1][0] + x);
1
2
3
4
5
6

时间复杂度：$O(n)$

代码

class Solution {
public:
    int minOperations(string s1, string s2, int x) {
        vector<int> p;
        for (int i = 0; i < s1.size(); ++i) 
            if (s1[i] != s2[i]) p.push_back(i);
        int m = p.size();
        if (m % 2 == 1) return -1;
        if (m == 0) return 0;

        vector<vector<int>> f(m + 1, vector<int>(2, 0x3f3f3f3f));
        f[0][0] = 0;
        f[1][1] = x;
        for (int i  = 2; i <= m; ++i) {
            // 第 i 位选择操作 2
            f[i][0] = min(f[i][0], f[i - 2][0] + p[i - 1] - p[i - 2]);
            f[i][1] = min(f[i][1], f[i - 2][1] + p[i - 1] - p[i - 2]);
            // 第 i 位选择操作 1
            f[i][0] = min(f[i][0], f[i - 1][1]);
            f[i][1] = min(f[i][1], f[i - 1][0] + x);
        }

        return f[m][0];
    }
};
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