类比最长公共子序列的设计

定义：$dp_{i,j,k}$ 为 $a$ 的前 $i$ 个字符和 $b$ 的前 $j$ 个字符，取了 $a$ 的 $k$ 个子序列后，拼接起来等于 $b$ 的前 $j$ 个的方案数。

转移：

• 不使用 $a_i$, 则转移到 $dp_{i-1,j,k}$
• 使用 $a_i$, 即意味着 $a_i$ 作为取出的第 $k$ 段子串的最后一个。假如 $a_i=b_j$ 但是 $a_{i-1}\not= b_{j-1}$ 那么我们就可以转移到 $dp_{i-1,j-1,k-1}$ 。如果 $a_{i}=b_{j},a_{i-1}=b_{j-1},\dots$ ,同理我们还得转移到 $dp_{i-2,j-2,k-1}$ 。可以发现只要末尾连续一段的子串大家都相同，那么就得往前转移。即

$dp_{i,j,k}=dp_{i-1,j,k}+\sum dp_{i-t,j-t,k-1},a[i-t+1\sim i]==b[j-t+1\sim j]$，即后面的子串都相同就需要转移。

至此你获得了 $70$ 分，枚举状态是 $O(nmk)$ 的，转移还需要枚举子串，复杂度较高，但也不算低分。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e2 + 5, p = 1e9 + 7;
int n, m, K;
string a, b;
int f[N][55][55];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> K;
    cin >> a >> b;
    a = " " + a, b = " " + b;
    //a的前0个和b的前0个取出0的子串的方案数为1
    f[0][0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            //a的前i个b的前0个取出0的子串的方案数为1
            f[i][0][0] = 1;
            for (int k = 1; k <= K; k++)
            {
                f[i][j][k] = f[i - 1][j][k];
                for (int t = 1; t <= min(i, j); t++)
                {
                    if (a.substr(i - t + 1, t) == b.substr(j - t + 1, t))
                    {
                        f[i][j][k] += f[i - t][j - t][k - 1];
                        f[i][j][k] %= p;
                    }
                }
            }
        }
    }
    cout << f[n][m][K];
    return 0;
}

考虑优化，主要在于转移的部分，发现转移的部分是前面已经计算好的一段 $dp$ 数组的和，那么能否再计算的途中就维护好这个数值？

我们设 $sum_{i,j,k}$ 为 $\sum dp_{i-t,j-t,k-1}$ 同时维护的时候必然要保证最后一段连续的子串相等，才能累加，否则应该重置为 $0$.

我们发现 $sum_{i-1,j-1,k}$ 就是 $dp_{i-2,j-2,k-1}+\dots$ 相比 $sum_{i,j,k}$ 就少了一项 $dp_{i-1,j-1,k-1}$

至此就得到了 $sum_{i,j,k}=sum_{i-1,j-1,k}+dp_{i-1,j-1,k-1}$

至此本题已经结束，发现空间接下来不够了，转移只和前 $1$ 项有关，可以使用滚动数组优化，或者类比 $01$ 背包的做法， 状态只跟前面一层小的状态有关，倒序枚举一维即可实现。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3 + 5, p = 1e9 + 7;
int n, m, K;
string a, b;
int f[205][205], sum[205][205];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> K;
    cin >> a >> b;
    a = " " + a, b = " " + b;
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= 1; j--)
        {
            for (int k = 1; k <= K; k++)
            {
                if (a[i] == b[j])  sum[j][k] = (sum[j - 1][k] + f[j - 1][k - 1]) % p;
                else sum[j][k] = 0;
                f[j][k] = (f[j][k] + sum[j][k]) % p;
            }
        }
    }
    cout << f[m][K];
    return 0;
}