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

[Anonymous]

Я пытаюсь решить проблему LeetCode 1653. Минимальное количество удалений, чтобы сделать строку сбалансированной:

Вам дана строка s, состоящая только из символы 'a' и 'b'​​​.
Вы можете удалить любое количество символов в s, чтобы получилось s сбалансированный. s является сбалансированным, если не существует пары индексов (i,j) такой, что i < j и s = 'b' и s[j]= 'a'.
Верните минимальное количество удалений, необходимое для создания s сбалансирован.
Ограничения:

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

  1 
  Удалить символы в позициях 3 и 6 с нулевым индексом («aababbab» -> «aabbbb»)
  
  Я понял оптимальным решением является использование DP или какого-либо итеративного подхода, но мне интересно, возможно ли это конкретно с помощью рекурсии.
  Изначально я сделал это:
  [code]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