Оптимизация решения динамического программирования для проблемы сокращений - Hackerrank ⇐ Python

[Anonymous]

Поэтому я лично предпочитаю кодировать решения динамического программирования, используя нисходящий подход. Особенно в Python, потому что он поддается довольно простой рекурсивной реализации с использованием декоратора кэша, как я объясню ниже.
А для проблемы сокращений на Hackerrank я набрал следующее решение (на самом деле это просто рекурсивное решение, использующее преимущества неявной мемоизации, которую мы можем получить от декоратора кэша).

Код: Выделить всё

def abbreviation(a, b):
n, m = len(a), len(b)

@lru_cache(maxsize=n*m)
def abbreviation_helper(i,j):
global a,b
if i < j:
return False

if j == -1:
if a == -1 or all([a[x].islower() for x in range(i)]):
return True
if a[i].isupper() and a[i] != b[j]:
return False

if a[i].upper() == b[j]:
return abbreviation_helper(i-1, j-1) or abbreviation_helper(i-1, j)
else:
return abbreviation_helper(i-1, j)

ret = abbreviation_helper(n-1,m-1)
if ret:
return "YES"
return "NO"

Это отлично работает и дает правильное решение; однако для некоторых из них время ожидания истекает (а именно, тестовые примеры: 10,12,13,14). Мой вопрос в том, могу ли я что-то сделать для дальнейшей оптимизации, чтобы время ожидания не истекло (сохраняя логику и подход кода в основном теми же). Я думал, что декоратора кэша будет достаточно, чтобы гарантировать, что он запустится в подходящее время, избегая избыточных вычислений. Однако, возможно, я делаю какие-то дополнительные звонки, которые не нужны. Если у кого-нибудь есть мысли, пожалуйста, дайте мне знать. Спасибо.
Что касается обозначения big o, мы знаем, что это асимптотически то же самое, что и использование восходящего подхода, так что же вызывает тайм-аут?
Я попробовал решение, используя подход «снизу вверх», и он отлично работает. У меня также изначально было решение, которое выполняло вызовы с аргументами, представляющими собой нарезанные строки, но я изменил вызовы, чтобы они принимали целые числа в качестве аргумента, в попытке дальнейшей оптимизации этого. Ожидал, что этого будет достаточно.

Подробнее здесь: https://stackoverflow.com/questions/790 ... hackerrank