第3题

const int mod = 1'000'000'007;
bool filled[maxn][maxn];
int mem[maxn][maxn];

int solve(int i, int j, int a[], int b[])
{
    if (i == 0 || j == 0) {
        return 1;
    }
    if (filled[i][j]) {
        return mem[i][j];
    }
    filled[i][j] = true;
    int sum = (solve(i - 1, j, a, b) + solve(i, j - 1, a, b)) % mod;
    if (a[i] == b[j]) {
        return mem[i][j] = sum;
    }
    else {
        return mem[i][j] = (sum - solve(i - 1, j - 1, a, b)) % mod;
    }
}

solve(n, m, a, b) 的最坏时间复杂度为（　）。

{{ select(1) }}

• $O(n+m)$
• $O(n\cdot m)$
• $O(2^{m+n})$
• $O(n\log m)$