Журнал 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.
Понимаете ли вы, что проблема, которую иначе называли сложной, на самом деле была проблемой, которая даже ниже легкой по сложности. Но если принять неправильный подход, эта проблема в кратчайшие сроки превратится в кошмар.
Итак, урок состоит в том, чтобы заставить клетки вашего мозга работать, изучить и опровергнуть формулировку проблемы, а затем приступить к решению проблемы. Не думайте о подходах, которые дают некоторый результат как побочный эффект в этом случае, генерируя подпоследовательности, когда требуется только подсчет.
Что дальше
Реализация вышеуказанной проблемы:
- Рекурсивный
- Памятный
- Итеративный
- Оптимизация пространства