Визуализация перекрывающихся подзадач в вопросе регулярного выражения LeetCode и использовании DP

Я просто решил эту проблему (10. Регулярное выражение) на leetcode.com, используя рекурсию. Я смог понять рекурсивное решение. Однако, когда я вижу оптимизированную версию этого кода, мне предлагается использовать динамическое программирование. Я не могу понять, зачем здесь нужно динамическое программирование?

• Я не вижу, чтобы эта проблема имела перекрывающиеся подзадачи. Зачем нам когда-либо использовать мемонирование или табуляцию? Я не могу визуализировать перекрывающиеся подзадачи.

• Здесь я дошел до сих пор. Это мое решение:

   public static boolean isMatch(String text, String pattern) {
  
  if (pattern.isEmpty())
      return text.isEmpty();
  boolean first_match = (!text.isEmpty() && (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
  
  if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
      return isMatch(text, pattern.substring(2))|| first_match && isMatch(text.substring(1), pattern);
  } else {
      return first_match && isMatch(text.substring(1), pattern.substring(1));
  }
  

Мое понимание рекурсивного решения состояло в том, что я мог видеть, является ли следующий символ в шаблоне *, тогда может быть два сценария:

1. Мы пропускаем текущий символ, а также следующий символ (*) и берем подстроку шаблона из индекса 2 и сопоставляем оставшуюся подстроку шаблона с текущим текстом. Это учитывает появление "0" для символа, предшествующего *.
2. * В шаблоне будет продолжать поглощать совпадающие символы из текста. Пока мы продолжаем получать тот же характер, они продолжают соответствовать звезде, и мы продолжаем идти вперед.

Другой сценарий: если следующий символ не является "*", тогда мы проверяем соответствие совпадающих символов, если да, тогда проверьте оставшиеся подстроки для обоих.

Я пробовал работать с этим:

Вход: s = "mississippi" p = "mis * is * p *." Выход: false

Я могу представить, что первые m и m соответствуют, я и я соответствуют (линейная рекурсия до сих пор). Теперь начинается сложная часть, потому что s и s соответствуют, но следующий символ - звезда. Если я вызываю, сопоставляя "0" в качестве сценария 1 и поглощая совпадающие символы в * как сценарий 2, тогда рекурсивные вызовы выглядят так:

Сценарий 1: текст ssissippi, а оставшийся шаблон isp.

s и я не совпадали

Сценарий 2: оставшийся текст - сиссиппи, а шаблон - sisp *.

Сценарий 1: текст sissippi, а оставшийся шаблон isp.

s и я не совпадали

Сценарий 2: оставшийся текст - isippi, а шаблон - sisp *.

Сценарий 1: текст isippi и оставшийся шаблон isp.

символы соответствуют следующему рекурсивному вызову с текстом: ssippi и pattern as: sp.

Сценарий 1: текст ssippi, а оставшийся шаблон - p *.

Сценарий 1: текст ssippi и оставшийся шаблон.

символы соответствуют следующему рекурсивному вызову с текстом: sippi и pattern as:

Сценарий 2: оставшийся текст - sippi, а pattern - p *.

Сценарий 2: оставшийся текст - сиппи, а шаблон - sp.

Сценарий 1: текст sippi, а оставшийся шаблон - p *.

Сценарий 1: текст - сиппи, а оставшийся шаблон -.

символы соответствуют следующему рекурсивному вызову с текстом: ippi и pattern as: Сценарий 2: оставшийся текст - ippi, а pattern - p *.

Сценарий 2: оставшийся текст - ippi, а шаблон - sp.

Сценарий 1: текст ippi, а оставшийся шаблон - p *.

Сценарий 1: текст ippi и оставшийся шаблон.

символы соответствуют следующему рекурсивному вызову с текстом: ppi и pattern as:

Сценарий 2: оставшийся текст - ppi, а шаблон - p *.

Сценарий 2: оставшийся текст - ppi, а шаблон - sp.

Сценарий 2: оставшийся текст - ssippi, а шаблон - sisp *.

И, наконец, верните False.

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

Я даже попытался взглянуть на youtube. Этот парень не говорит, как мы достигаем этого решения, он просто просто иссушает решение, потому что знает его проблему с DP.

Как мы выясним, является ли это проблемой DP? Какова интуиция в достижении решения DP для этой проблемы?

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

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