Общая подпоследовательность

Даны две строки. Из каждой можно вычёркивать любые символы, не меняя порядок оставшихся.

Какой наибольшей длины строку можно получить и из первой, и из второй?

В первой строке первая строка, во второй — вторая. Каждая состоит из строчных латинских букв, длина от $1$ до $1500$.

Одно число.

Состояние — «длина ответа для первых $i$ символов первой строки и первых $j$ второй». Если последние символы совпали, их выгодно взять оба; если нет, придётся отказаться от одного из них — и надо взять лучший из двух вариантов.