Журнал 0: проблема String Dp

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

Проблема: для строки S и строки T подсчитайте количество различных подпоследовательностей S, которые равны Т.

Подпоследовательность строки - это новая строка, которая формируется из исходной строки путем удаления некоторых (не обязательно) символов без нарушения относительного положения остальных символов. (т.е. "ACE" является подпоследовательностью "ABCDE", а "AEC" - нет).

Гарантированно, что ответ соответствует 32-битному целому числу со знаком.

Пример:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Итак, я столкнулся с этим вопросом, и это был первый раз, когда я его решал.

Подход новичков😂:

Итак, первый подход непрофессионала, который приходит в голову, - это выяснить все подпоследовательности S и сохранить те, которые различны и равны T.

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

Вот почему я называю этот подход подходом нубов, лол, !

Это неправильный путь, о котором я говорил!

Считайте это профессионалом 😎:

Итак, внимательно изучив проблему, я обнаружил закономерность. Я, вы прочитали правильно f’ing pattern. Как вы думаете, в чем может быть узор ????

Итак, давайте разберемся, что дано в задаче.

  • Строка S или, мы можем сказать, массив символов, верно!
  • Строка T, которую мы должны создать, используя массив символов S.
  • Нам нужно найти несколько способов сделать T с помощью S.

Так что если вы внимательно изучите три приведенных выше пункта, вам не составит труда понять, что шаблон, о котором мы говорили, принадлежит к семейству Coin Change. Да, вы прочитали правильно, Coooooooiiiin Chchaaange.

Рассмотрим данное утверждение в задаче размены монеты.

  • Массив C стоимости монет.
  • Значение V, которое мы должны получить с помощью C.
  • Количество способов сделать V с помощью C.

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

Итак, урок состоит в том, чтобы заставить клетки вашего мозга работать, изучить и опровергнуть формулировку проблемы, а затем приступить к решению проблемы. Не думайте о подходах, которые дают некоторый результат как побочный эффект в этом случае, генерируя подпоследовательности, когда требуется только подсчет.

Что дальше

Реализация вышеуказанной проблемы:

  • Рекурсивный
  • Памятный
  • Итеративный
  • Оптимизация пространства