题目

520. 子串

思路

设计状态表示$f[i][j][k]$表示$a$的前$i$个字符, $b$的前$j$个字符, 并且已经分割了$k$个子串的所有方案, 将状态划分为包含第$i$个字符和不包含第$i$个字符, 不包含第$i$个字符的状态是$f[i-1][j][k]$, 包含第$i$个字符要按照最后一段的长度进行划分, 状态转移方程如下

f [ i ] [ j ] [ k ] = f [ i − 1 ] [ j ] [ k ] + { f [ i − 1 ] [ j − 1 ] [ k − 1 ] + f [ i − 2 ] [ j − 2 ] [ k − 1 ] + . . . + f [ i − t ] [ j − t ] [ k − 1 ] } f[i][j][k] = f[i - 1][j][k] + \left \{ f[i - 1][j - 1][k - 1] + f[i - 2][j - 2][k - 1] + ... + f[i - t][j - t][k - 1]\right \} f[i][j][k]=f[i−1][j][k]+{f[i−1][j−1][k−1]+f[i−2][j−2][k−1]+...+f[i−t][j−t][k−1]}

其中$t\le j$, 计算时间复杂度$1000\times 200\times 200\times 200=8\times 10^9$会超时, 因此需要进行优化

观察$f[i-1][j-1][k]$的状态转移方程

f [ i − 1 ] [ j − 1 ] [ k ] = f [ i − 2 ] [ j ] [ k ] + { f [ i − 2 ] [ j − 2 ] [ k − 1 ] + f [ i − 3 ] [ j − 2 ] [ k − 1 ] + . . . + f [ i − t ] [ j − t ] [ k − 1 ] } f[i - 1][j - 1][k] = f[i - 2][j][k] + \left \{ f[i - 2][j - 2][k - 1] + f[i - 3][j - 2][k - 1] + ... + f[i - t][j - t][k - 1]\right \} f[i−1][j−1][k]=f[i−2][j][k]+{f[i−2][j−2][k−1]+f[i−3][j−2][k−1]+...+f[i−t][j−t][k−1]}

我们发现大括号中很大一部分是重合的, 设大括号中的部分是$s[i][j][k]$, 那么观察到$s[i][j][k]=s[i-1][j-1][k]+f[i-1][j-1][k-1]$, 因此可以少枚举一维, 状态转移方程变为$f[i][j][k]=f[i-1][j][k]+s[i][j][k]$

计算空间复杂度$1000\times 200\times 200\times 4byte$, 大约是$400MB$, 但是空间限制只有$128MB$, 因此空间上也需要优化, 常见的空间优化方式滚动数组

*超过空间限制

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1010, M = 210, MOD = 1e9 + 7;int n, m, cnt;
string a, b;
int f[N][N][M], s[N][N][M];int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m >> cnt;cin >> a >> b;a = " " + a;b = " " + b;f[0][0][0] = 1;for (int i = 1; i <= n; ++i) {for (int j = 0; j <= m; ++j) {for (int k = 0; k <= cnt; ++k) {if (a[i] != b[j]) s[i][j][k] = 0;else if (j) {s[i][j][k] = s[i - 1][j - 1][k];if (k) s[i][j][k] = (s[i - 1][j - 1][k] + f[i - 1][j - 1][k - 1]) % MOD;}f[i][j][k] = (f[i - 1][j][k] + s[i][j][k]) % MOD;}}}int res = f[n][m][cnt];cout << res << "\n";return 0;
}

$01$背包优化方式

注意到, 由于每一层状态只与上一层状态有关, 观察状态转移方程$f[i][j][k]=f[i-1][j][k]+s[i][j][k]$, 并且$s[i][j][k]=s[i-1][j-1][k]+f[i-1][j-1][k-1]$, 也就是说第二维的状态也是取决于比它小的状态, 因此可以优化掉一维, 对于第二维因为要用到比它小的位置的状态, 需要从后向前枚举

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1010, M = 210, MOD = 1e9 + 7;int n, m, cnt;
string a, b;
int f[N][M], s[N][M];int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m >> cnt;cin >> a >> b;a = " " + a;b = " " + b;f[0][0] = 1;for (int i = 1; i <= n; ++i) {for (int j = m; j; --j) {for (int k = 1; k <= cnt; ++k) {if (a[i] != b[j]) s[j][k] = 0;else s[j][k] = (s[j - 1][k] + f[j - 1][k - 1]) % MOD;f[j][k]=  (f[j][k] + s[j][k]) % MOD;}}}cout << f[m][cnt] << "\n";return 0;
}

滚动数组优化方式

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1010, M = 210, MOD = 1e9 + 7;int n, m, cnt;
string a, b;
int f[2][N][M], s[2][N][M];int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m >> cnt;cin >> a >> b;a = " " + a;b = " " + b;f[0][0][0] = 1;for (int i = 1; i <= n; ++i) {for (int j = 0; j <= m; ++j) {for (int k = 0; k <= cnt; ++k) {if (a[i] != b[j]) s[i & 1][j][k] = 0;else if (j) {s[i & 1][j][k] = s[i - 1 & 1][j - 1][k];if (k) s[i & 1][j][k] = (s[i - 1 & 1][j - 1][k] + f[i - 1 & 1][j - 1][k - 1]) % MOD;}f[i & 1][j][k] = (f[i - 1 & 1][j][k] + s[i & 1][j][k]) % MOD;}}}int res = f[n & 1][m][cnt];cout << res << "\n";return 0;
}