Если вы не понимаете динамическое программирование, это бесполезно.

алгоритм

Есть определенные правила, которым нужно следовать, найдите распорядок.

Что такое динамическое программирование.

Сколько способов попасть в правый нижний угол (это можно сделать только при динамическом программировании) Вывести все пути, ведущие в правый нижний угол (рекурсия dfs)

Классификация тем:

  1. считать Сколько способов попасть в правый нижний угол Сколькими способами можно выбрать K чисел так, чтобы сумма была равна сумме
  2. Найдите максимум и минимум Максимальное значение и сумма пути из левого нижнего угла в правый нижний угол самая длинная восходящая длина подпоследовательности
  3. искать существование В игре со сбором камней обязательно ли выиграет тот, кто сделает первый ход? Можем ли мы выбрать K чисел так, чтобы сумма была Sum

coin change

В наличии 3 монеты, номинал: 2 юаня, 5 юаней, 7 юаней, хватит на каждую монету

Купить книгу стоит 27 юаней.

Как расплатиться наименьшей комбинацией монет, чтобы другая сторона не просила денег (ищем максимальное и минимальное значения)

Забудьте о динамическом программировании: интуиция: Старайтесь использовать крупные монеты, если в итоге сможете расплатиться одной монетой.

Интуитивный ответ неверен.

Динамическая 4-шаговая ходьба:

1. Определить состояние (Dinghaishenzhen)

  • Чтобы решить динамическое программирование, вам нужно открыть массив Что представляет каждый элемент массива f[i] или f[i][j]?

    • Подобно решению математики, что представляют собой X, Y, Z (укажите)

  • Для определения состояния требуется два значения:

    • последний шаг

      • Хотя я не знаю, какова оптимальная стратегия, оптимальной стратегией должно быть K монет a1, a2,....ak. Сумма номинала равна 27.
      • Так что должна быть последняя монета :ak
      • Уберите эту монету и номиналы предыдущих монет в сумме составят 27-ак
      • Нам все равно, как на монете К-1 пишется 27-ak (может быть, 1 написание, может быть, 100 написаний), и мы даже не знаем сейчас ak и k, но мы уверены, что предыдущая монета пишется как Out of 27. -ak (последний шаг, определенный в неопределенности)
      • Ключ: Потому что это оптимальная стратегия, потому что количество монет, на которых пишется 27-ак, должно быть наименьшим, иначе это не оптимальная стратегия.Независимо от последней монеты, написание оставшихся монет также является оптимальной стратегией .

    • Подвопрос:

      • Следовательно, минимальное количество монет, используемых для написания 27-ak
      • Первоначальный вопрос заключался в том, сколько монет нужно использовать, чтобы составить число 27.
      • Преобразуем исходную задачу в подзадачу меньшего размера: 27-ak
      • Чтобы упростить определение, мы установили f (X) = минимальное количество монет для написания X.

    • Даже проанализировав последний шаг и подзадачи, я до сих пор не знаю, что такое последняя монета.

    • Последняя монета ак может быть только 2,5,7

      • Если ak=2, f(27)= должно быть f(27-2)+1
      • Если ak=5, f(27)= должно быть f(27-5)+1
      • Если ak=7, f(27)= должно быть f(27-7)+1
      • Кроме этого, нет никакой другой возможности.
      • Необходимое минимальное количество монет:
      • f(27) = min{f(27-2)+1,f(27-5)+1,f(27-7)+1} +1

Рекурсивное решение:

Анализ рекурсивного алгоритма:

Феномен:

  • f(20) повторяется 3 раза
  • f(15) повторяется дважды

результат:

Делается много избыточных повторных вычислений, что неэффективно.

Как этого избежать?

  1. сохранить результат расчета
  2. и изменить порядок вычислений.

2. Уравнение переноса

  • Пусть состояние f[X] = минимальное количество монет для написания X (Квадратные скобки обозначают массивы)
  • Для любого Х:
  • На данный момент проблема динамического программирования наполовину решена.

3. Начальные условия и краевые задачи.

После определения уравнения переноса необходимо определить начальные условия и граничные задачи.

  • f[27] = min{f[27-2]+1,f[27-5]+1,f[27-7]+1} +1
  • Два вопроса: что делать, если X-2, X-5 или X-7 меньше 0. Когда остановиться?
  • Если Y нельзя указать, определите f[Y] = положительная бесконечность
    • Например, f[-1]=f[-2]=положительная бесконечность
    • В реальной работе f[-1] не будет открываться.
  • Таким образом, f[1]= min{f[-1]+1,f[-4]+1,f[-6]+1}= положительная бесконечность, что означает, что 1 нельзя написать по буквам
  • Первоначальные условия:f[0] = 0

4. Определяем порядок расчета

  • Начальное условие: f[0]= 0
  • Затем вычислить f[1], f[2], f[3].... в порядке возрастания (обычно пошаговые вычисления)
  • Преимущества: Но когда мы вычисляем f[X], f[X-2], f[X-5], f[X-7] уже получили результат,Избегайте двойного счета

временная сложность:

O(n)= n

Суммировать:

  1. Динамическое программирование предпочтительнее для поиска наиболее ценного типа.
  2. определить статус
    • Последний шаг: последняя монета, используемая в оптимальной политике ak
    • Преобразование в подзадачи: укажите наименьшее количество монет с меньшим номиналом 27-ak
  3. Определите уравнение переноса: f[X] = min{f[X-2]+1,f[X-5]+1,f[X-7]+1}+1
  4. Определить начальные условия и граничные случаи: f[0]=0, не могу разобрать, F[X] = положительная бесконечность
  5. Определяем порядок вычислений: f[0]-->f[1]-->f[2]....

Эксклюзивный мастер-код искусственного интеллекта My Didi Cloud: 3388, Введите мастер-код, чтобы получить скидку 10% при покупке продуктов AI, таких как Didi Cloud GPU. нажмитеwww.didiyun.comПерейдите на официальный сайт Didi Cloud, чтобы купить

Эта статья опубликована на многопостовой платформеArtiPubавтоматическая публикация

Категории