Почему это работает
- Если последние буквы двух префиксов равны, какая-то наибольшая общая подпоследовательность кончается этой буквой: что бы ответ ни взял вместо неё, это можно заменить на неё. Значит, клетка — диагональ плюс один.
- Если они разные, хотя бы одна из двух букв не стоит в конце ответа, поэтому ответ — в клетке сверху или слева: большее из двух.
- Каждая клетка читает только клетки с префиксами короче, а они при обходе по строкам уже заполнены. Общая буква не на своём месте, как p здесь, к счёту ничего не добавляет.
Сложность
Время O(n × m) для слов длины n и m: по клетке на каждую пару префиксов, каждая считается по трём соседям. Память O(n × m) на таблицу; если хранить только строку сверху, будет O(m).
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗