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

Java алгоритм

предисловие

Когда мы чистим leetcode, мы часто сталкиваемся с проблемами типа динамического программирования. Задачи динамического программирования очень, очень классические и очень технические, и обычно крупные производители любят их задавать. Сегодня давайте вместе с вами изучим рутину динамического программирования, если в статье что-то не так, укажите на это, спасибо~

  • Что такое динамическое программирование?
  • Основная идея динамического программирования
  • Пример динамического программирования
  • Процедуры решения задач динамического программирования
  • пример использования литкода

публика:маленький мальчик собирает улиток

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

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

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

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

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

Основная идея динамического программирования

Основная идея динамического программирования заключается в том, чтоРазделите подзадачи, вспомните прошлое и уменьшите двойной счет.

动态规划在于记住过往

Давайте рассмотрим пример, который популярен в Интернете:

  • A: "1+1+1+1+1+1+1+1 =?"
  • A: «Каково значение приведенного выше уравнения»
  • B : Вычислить "8"
  • О: Как насчет того, чтобы написать «1+» в левой части приведенного выше уравнения?
  • A: «Каково значение уравнения в данный момент?»
  • Б : Быстрый ответ "9"
  • А: "Как ты так быстро узнал ответ"
  • A: «Просто прибавьте 1 к 8».
  • A: «Таким образом, вам не нужно пересчитывать, потому что вы помните, что значение первого уравнения равно 8! Можно также сказать, что алгоритм динамического программирования «запоминает решение для экономии времени»»

Пример перенесет вас в динамическое программирование — задача о прыжках лягушки.

рекурсия грубой силы

Оригинальное название leetcode: Лягушка может прыгать на 1 ступеньку за раз или на 2 ступеньки за раз. Найдите, сколькими способами лягушка может запрыгнуть на 10-уровневую лестницу.

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

  • Чтобы перейти к 10-му шагу, либо перейдите к 9-му шагу, а затем на 1 шаг вверх, либо перейдите к 8-му шагу, а затем сделайте 2 шага за раз.
  • Таким же образом, чтобы перейти на 9-й шаг, либо прыгнуть сначала на 8-й шаг, а затем на 1-й шаг, либо прыгнуть сначала на 7-й шаг, а затем сделать 2-й шаг за раз.
  • Чтобы перейти на 8-й шаг, либо перейдите на 7-й шаг, а затем на 1 шаг вверх, либо прыгните на 6-й шаг, а затем поднимитесь на 2 шага за раз.

Предполагая, что количество переходов на n-й шаг определяется как f(n), очевидно, что можно получить следующую формулу:

f（10） = f（9）+f(8)
f (9)  = f(8) + f(7)
f (8)  = f(7) + f(6)
...
f(3) = f(2) + f(1)

即通用公式为: f(n) = f(n-1) + f(n-2)

Так чему же равно f(2) или f(1)?

  • Когда есть только 2 шага, есть два способа прыжка: первый — прыгать сразу на два шага, а второй — прыгать сначала на один шаг, а затем на другой. т. е. f(2) = 2;
  • Когда есть только 1 шаг, есть только один способ прыжка, то есть f(1) = 1;

Таким образом, вы можете использовать рекурсию для решения этой проблемы:

class Solution {
    public int numWays(int n) {
    if(n == 1){
        return 1;
    }
     if(n == 2){
        return 2;
    }
    return numWays(n-1) + numWays(n-2);
    }
}

Перейдите в leetcode, чтобы отправить его, и обнаружите, что есть проблема, превышающая лимит времени.

Почему время истекло? Где рекурсия занимает много времени? нарисуй первымдерево рекурсииВзгляни:

  • Для вычисления исходной задачи f(10) необходимо сначала вычислить подзадачи f(9) и f(8)
  • Затем вычисляется f(9), сначала вычисляются подзадачи f(8) и f(7) и так далее.
  • Дерево рекурсии не заканчивается до f(2) и f(1).

Давайте сначала посмотрим на временную сложность этой рекурсии:

递归时间复杂度 = 解决一个子问题时间*子问题个数
  • Время подзадачи = f(n-1) + f(n-2), что является операцией сложения, поэтому сложность равна O(1);
  • Количество проблем = общее количество узлов рекурсивного дерева, общее количество узлов рекурсивного дерева = 2 ^ n-1, поэтому сложность составляет O (2 ^ n).

Следовательно, лягушка прыгает, временная сложность рекурсивного решения = O (1) * O (2 ^ n) = O (2 ^ n), что является экспоненциальным и взрывным ростом.Если n относительно велико, тайм-аут нормальный . . .

Оглядываясь назад, если вы внимательно посмотрите на это дерево рекурсии, вы обнаружите, что существует множество повторяющихся вычислений, например, f(8) вычисляется дважды, f(7) повторяется трижды... Таким образом, этот рекурсивный алгоритм неэффективно Причина в том, чтоМного двойного счета!

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

Рекурсивное решение с мемоизацией (сверху вниз)

Обычно в качестве этого используется массив или хэш-карта.меморандум.

  • На первом этапе f(10) = f(9) + f(8), необходимо рассчитать как f(9), так и f(8), а затем добавить в памятку следующим образом:

  • Второй шаг, f(9) = f(8) + f(7), f(8) = f(7) + f(6), поскольку f(8) уже есть в меморандуме, поэтому его можно опустить. , Обе f(7) и f(6) должны быть рассчитаны и добавлены в памятку~

Третий шаг, f(8) = f(7) + f(6), показал, что f(8), f(7), f(6) все есть в служебной записке, поэтому их можно отрезать.

Итак, используя алгоритм рекурсии мемо, рекурсивное дерево становится голым стволом, как показано ниже:

поясмеморандумРекурсивный алгоритм , количество подзадач = количеству узлов дерева = n, решение подзадачи по-прежнему O (1), поэтому смеморандумВременная сложность рекурсивного алгоритма составляет O(n). Далее мы используеммеморандумРекурсивный алгоритм используется для написания кода для решения проблемы тайм-аута этой задачи о прыжках лягушки.Код выглядит следующим образом:

public class Solution {
    //使用哈希map，充当备忘录的作用
    Map<Integer, Integer> tempMap = new HashMap();
    public int numWays(int n) {
        // n = 0 也算1种
        if (n == 0) {
            return 1;
        }
        if (n <= 2) {
            return n;
        }
        //先判断有没计算过，即看看备忘录有没有
        if (tempMap.containsKey(n)) {
            //备忘录有，即计算过，直接返回
            return tempMap.get(n);
        } else {
            // 备忘录没有，即没有计算过，执行递归计算,并且把结果保存到备忘录map中，对1000000007取余（这个是leetcode题目规定的）
            tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);
            return tempMap.get(n);
        }
    }
}

Перейдите в leetcode и отправьте его, как показано на рисунке, он стабилен:

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

Динамическое программирование снизу вверх

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

  • Рекурсия с мемо расширяется от f(10) до f(1), поэтому она также называетсянизходящийрешение.
  • Из решения меньшей проблемы динамическое программирование постепенно решает решение большей проблемы из решения меньшей проблемы.вверх дномрешение.

Динамическое программирование имеет несколько типичных характеристик,Оптимальная подструктура, уравнения перехода состояний, границы, перекрывающиеся подзадачи. В задаче о прыжках лягушки:

  • f(n-1) и f(n-2) называются оптимальными подструктурами f(n)
  • f (n) = f (n-1) + f (n-2) называется уравнением перехода состояния
  • f(1) = 1, f(2) = 2 — граница
  • Например, f(10)= f(9)+f(8), f(9) = f(8) + f(7) , f(8) — это перекрывающаяся подзадача.

Давайте посмотрим на восходящее решение, от f(1) до f(10), и подумаем, можно ли его решить напрямую с помощью цикла for следующим образом:

Рекурсивное решение с памяткой имеет пространственную сложность O (n).Однако, если вы внимательно посмотрите на рисунок выше, вы обнаружите, что f (n) зависит только от первых двух чисел, поэтому только две переменные a и b необходимы для их хранения Это может удовлетворить спрос, поэтому сложность пространства O (1).

Код реализации динамического программирования выглядит следующим образом:

public class Solution {
    public int numWays(int n) {
        if (n<= 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int a = 1;
        int b = 2;
        int temp = 0;
        for (int i = 3; i <= n; i++) {
            temp = (a + b)% 1000000007;
            a = b;
            b = temp;
        }
        return temp;
    }
    }

Процедуры решения задач динамического программирования

Какие проблемы вы можете решить с помощью динамического программирования?

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

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

Идеи решения проблем динамического программирования

Основная идея динамического программирования заключается в том,Разделите подзадачи, вспомните прошлое и уменьшите двойной счет.А динамическое программирование вообще восходящее, поэтому здесь, на основелягушка прыгает по ступенькамВопрос, я резюмировал свои идеи по динамическому программированию:

  • исчерпывающий анализ
  • определить границы
  • Узнайте правила и определите оптимальную подконструкцию
  • Напишите уравнение перехода состояния

1. Исчерпывающий анализ

  • Когда количество шагов равно 1, есть метод прыжка, f(1) = 1
  • Когда есть только 2 шага, есть два способа прыжка: первый — прыгать сразу на два шага, а второй — прыгать сначала на один шаг, а затем на другой. т. е. f(2) = 2;
  • Когда шагов 3, если вы хотите перейти на 3-й шаг, вы можете либо перейти сначала на 2-й шаг, а затем перейти на 1 шаг вверх, либо вы можете сначала перейти на 1-й шаг, а затем подняться на 2 шага за раз. . Итак, f(3) = f(2) + f(1) = 3
  • Когда шагов 4, если вы хотите перейти к 3-му шагу, вы можете либо сначала перейти к 3-му шагу, а затем перейти на 1 шаг вверх, либо вы можете сначала перейти ко 2-му шагу, а затем подняться на 2 шага за раз. . Итак, f(4) = f(3) + f(2) = 5
  • Когда шаги уровня 5...

自底向上的动态规划

2. Определите границы

Путем исчерпывающего анализа мы обнаружили, что когда количество шагов равно 1 или 2, способ прыжка лягушки может быть четко известен. f(1) = 1, f(2) = 2, при шаге n>=3 выполняется закон f(3) = f(2) + f(1) = 3, поэтому f(1) = 1, f (2) = 2 – граница прыжков лягушки.

3. Найдите правила и определите оптимальную подструктуру

Когда n>=3, был показан закон f(n) = f(n-1) + f(n-2), поэтому f(n-1) и f(n-2) называются f(n) оптимальная подструктура . Какова оптимальная подструктура? Есть такое объяснение:

Проблема динамического программирования на самом деле является проблемой рекурсии. Если предположить, что текущим результатом решения является f(n), оптимальная подструктура состоит в том, чтобы сделать f(nk) оптимальной, а природа оптимальной подструктуры состоит в том, чтобы сделать переход в состояние n оптимальным, и это не имеет ничего общего с последующие решения. , то есть свойство, которое позволяет последующим решениям безопасно использовать предыдущее локальное оптимальное решение

4. Напишите уравнение перехода состояния

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

5. Реализация кода

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

dp[0][0][...] = 边界值
for(状态1 ：所有状态1的值){
    for(状态2 ：所有状态2的值){
        for(...){
          //状态转移方程
          dp[状态1][状态2][...] = 求最值
        }
    }
}

пример использования литкода

Давайте проанализируем классическую проблему с литкодом

Дан массив целых чисел nums , найти в нем длину самой длинной строго возрастающей подпоследовательности.

Пример 1:

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

Пример 2:

输入：nums = [0,1,0,3,2,3]
输出：4

Согласно приведенной выше идее динамического программирования для решения проблем,

  • исчерпывающий анализ
  • определить границы
  • Найдите закон и определите оптимальную подструктуру
  • уравнение перехода состояния

1. Исчерпывающий анализ

Из-за динамического программирования основные идеи включаютРазделите подзадачи, вспомните прошлое и уменьшите двойной счет.Итак, мы думаем над исходным вопросом:Когда самая длинная возрастающая длина подпоследовательности массива num[i], вы можете подумать оСвязанные подвопросы, например, связана ли исходная проблема сподзадачаКак насчет самой длинной возрастающей подпоследовательности num[i-1]?

исчерпывающее пополнение

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

  • Когда nums имеет только один элемент, 10, самая длинная возрастающая подпоследовательность — это [10], а длина равна 1.
  • Когда nums нужно добавить элемент 9, самая длинная возрастающая подпоследовательность — это [10] или [9], а длина равна 1.
  • Когда элемент 2 добавляется к nums, самая длинная возрастающая подпоследовательность будет [10], [9] или [2], а длина равна 1.
  • Когда элемент 5 добавляется к nums, самая длинная возрастающая подпоследовательность будет [2,5], а длина равна 2.
  • Когда nums добавляет еще один элемент 3, самая длинная возрастающая подпоследовательность будет [2,5] или [2,3], а длина равна 2.
  • Когда элемент 7 добавляется к nums, самая длинная возрастающая подпоследовательность будет [2,5,7] или [2,3,7], а длина равна 3.
  • Когда nums добавляет еще один элемент 101, самая длинная возрастающая подпоследовательность будет [2,5,7,101] или [2,3,7,101], а длина равна 4.
  • Когда nums добавляет еще один элемент 18, самая длинная возрастающая подпоследовательность будет [2,5,7,101] или [2,3,7,101] или [2,5,7,18] или [2,3,7,18] , длина это 4.
  • Когда элемент 7 добавляется к nums, самая длинная возрастающая подпоследовательность будет [2,5,7,101] или [2,3,7,101] или [2,5,7,18] или [2,3,7,18] , длина 4.
Анализ для поиска правил, разделения подзадач

С помощью приведенного выше анализа мы можемнайти правило:

Если к nums[i] добавляется новый элемент, самая длинная возрастающая подпоследовательность либоявляется возрастающей подпоследовательностью, оканчивающейся на nums[i], либосамая длинная возрастающая подпоследовательность чисел[i-1]. Вы очень рады видеть это, самая длинная возрастающая подпоследовательность nums[i] сопровождаласьподзадачаАссоциируется самая длинная возрастающая подпоследовательность nums[i-1].

原问题数组nums[i]的最长递增子序列 = 子问题数组nums[i-1]的最长递增子序列/nums[i]结尾的最长递增子序列

Вы чувствуете, что уже на полпути? ноКак преобразовать возрастающую подпоследовательность в конце nums[i] в ​​соответствующую подзадачуШерстяная ткань? Было бы неплохо, если бы возрастающая подпоследовательность в конце nums[i] также была связана с самой длинной возрастающей подпоследовательностью nums[i-1]. Или самая длинная возрастающая подпоследовательность в конце nums[i] связана с самой длинной возрастающей подпоследовательностью в конце предыдущей подзадачи num[j] (0=

самая длинная возрастающая подпоследовательность nums[i], либоИз самого длинного набора подпоследовательностей, заканчивающегося каждым элементом массива num[i], выберите тот, у которого больше всего элементов (то есть самая длинная длина)., поэтому исходная задача, мы преобразуем ее, чтобы найти самый длинный набор подпоследовательностей, заканчивающийся каждым элементом массива nums, а затем береммаксимальное значениеЧто ж. Ха-ха, имея это в виду, мы можемИспользуйте dp[i] для обозначения длины самой длинной возрастающей подпоследовательности, заканчивающейся числом num[i]Что ж, давайте посмотрим на правила:

фактически,Самоувеличивающаяся подпоследовательность в конце nums[i], если найдена подпоследовательность меньше, чем nums[i], добавить nums[i]Вот и все. Очевидно, что может образоваться множество новых подпоследовательностей, мы выбираем самую длинную, которая является значением dp[i].

  • nums[3]=5, с5Самая длинная подпоследовательность в конце[2,5], потому что индексация из массива0到3Обход, поиск только подпоследовательностей[2]Сравнивать5маленький, так[2]+[5]Ла, то естьdp[4]=2
  • числа[4]=3, с3Самая длинная подпоследовательность в конце[2,3], потому что индексация из массива0到4Обход, поиск только подпоследовательностей[2]Сравнивать3маленький, так[2]+[3]Ла, то естьdp[4]=2
  • числа[5]=7, с7Самая длинная подпоследовательность в конце[2,5,7]и[2,3,7], потому что индексация из массива0到5пройти, найти2,5和3меньше 7, поэтому[2,7],[5,7],[3,7],[2,5,7]和[2,3,7]Эти подпоследовательности, самая длинная подпоследовательность[2,5,7]和[2,3,7], они не5окончание и3Самая длинная возрастающая подпоследовательность в конце идет от +[7]! так,dp[5]=3 =dp[3]+1=dp[4]+1.

Очевидно, есть такое правило: массив nums, оканчивающийся на nums[i]

  • Если есть j, принадлежащий интервалу [0, i-1], и num[i]>num[j], то dp(i) =max(dp(j))+1,

Самый простой пограничный случай

Когда массив nums имеет только один элемент, длина самой длинной возрастающей подпоследовательности равна dp(1)=1, когда массив nums состоит из двух элементов, dp(2)=2 или 1, Таким образом, оценка dp(1)=1.

Определить оптимальную подструктуру

Из исчерпывающего анализа мы можем вывести следующую оптимальную структуру:

dp(i) =max(dp(j))+1，存在j属于区间[0，i-1],并且num[i]>num[j]。

max(dp(j))является оптимальной подструктурой.

уравнение перехода состояния

Проведя предыдущий анализ, мы можем получить уравнение перехода состояния:

Таким образом, самая длинная возрастающая подпоследовательность массива num[i] равна:

最长递增子序列 =max(dp[i])

Код

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        //初始化就是边界情况
        dp[0] = 1;
        int maxans = 1;
        //自底向上遍历
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            //从下标0到i遍历
            for (int j = 0; j < i; j++) {
                //找到前面比nums[i]小的数nums[j],即有dp[i]= dp[j]+1
                if (nums[j] < nums[i]) {
                    //因为会有多个小于nums[i]的数，也就是会存在多种组合了嘛，我们就取最大放到dp[i]
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            //求出dp[i]后，dp最大那个就是nums的最长递增子序列啦
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}

Ссылка и спасибо

  • официальный сайт литкода
  • "шпаргалка по алгоритму Лабуладонг"

Категории