При рекурсивном подходе к этой проблеме 25-й/1307-й тестовые случаи потребовали тайм-аута. По большей части рекурсия медленнее и занимает больше стека вызовов. Возьмем, к примеру, строку 9. Это вызов lcs для двух частей (i+1, j) и (i, j+1). После первых двух итераций становится ясно, что эта функция вызвала lcs для тех же значений i и j. Повторный вызов одной и той же функции и параметра не приводит к оптимизации и увеличивает стек вызовов до такой степени, что мы достигаем..