Можно ли решить LeetCode 1653 с помощью рекурсии? ⇐ Python

[Anonymous]

Картина проблемы

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

You are given a string s consisting only of characters 'a' and 'b'​​​​.

You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.

Return the minimum number of deletions needed to make s balanced.

Constraints:
1  "aabbbb")

Я пытаюсь решить 1653 из LeetCode. Я понимаю, что оптимальным решением является использование DP или какого-либо итеративного подхода, но мне интересно, возможно ли это конкретно с помощью рекурсии
Изначально я сделал это

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

class Solution:
def minimumDeletions(self, s: str) -> int:

@lru_cache(None)
def dfs(index, last_char):
if index == len(s):
return 0

if s[index] >= last_char:
keep = dfs(index + 1, s[index])
delete = 1 + dfs(index + 1, last_char)
return min(keep, delete)
else:
return 1 + dfs(index + 1, last_char)
return dfs(0, 'a')

Но это не было сокращением путей, которые уже превышают ранее найденный минимум, что вполне справедливо, поэтому я попробовал это дальше

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

class Solution:
def minimumDeletions(self, s: str) -> int:
self.min_deletions = float('inf')
memo = {}

def dfs(index, last_char, current_deletions):
if current_deletions >= self.min_deletions:
return float('inf')

if index == len(s):
self.min_deletions = min(self.min_deletions, current_deletions)
return 0

if (index, last_char) in memo:
return memo[(index, last_char)]

if s[index] >= last_char:
keep = dfs(index + 1, s[index], current_deletions)
delete = 1 + dfs(index + 1, last_char, current_deletions + 1)
result = min(keep, delete)
else:
result = 1 + dfs(index + 1, last_char, current_deletions + 1)

memo[(index, last_char)] = result
return result

return dfs(0, 'a', 0)

Кажется, он проходит тестовые случаи, когда я пытаюсь запустить его на 300 мс, но когда я пытаюсь отправить решение, я получаю ошибку превышения лимита памяти. Как лучше всего решить эту проблему с помощью рекурсии?

Подробнее здесь: https://stackoverflow.com/questions/788 ... -recursion