Понимание динамического программирования в одной статье

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

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

Так почему же динамическое программирование так важно на собеседованиях?

На самом деле, основная причина в том, что динамическое программирование очень подходит для интервью, потому что динамическое программирование не может «вернуться».

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

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

Например, в LeetCode есть 1261 тема алгоритмов, из которых темы динамического программирования занимают почти 200, а динамическое программирование может составлять 1/6 от общего числа тем, что показывает его популярность.

Что еще более важно, сложность динамического программирования в основном от средней до высокой сложности:

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

Начните с «денег»

В предыдущем содержании мы узнали, что жадный алгоритм может решить «проблему размена монет», но решить ее можно только в некоторых случаях, потому что номиналы монет, указанные в вопросе, равны 1, 5 и 25. В нашей реальной жизни наш текущий пятый набор номиналов юаней — это 100, 50, 20, 10, 5 и 1. Наш юань можно изменить с помощью жадного алгоритма.

Так есть ли ситуация, когда нельзя использовать жадный алгоритм? Например, центральный банк планеты алгоритмов выпустил замечательные монеты номиналом 1, 5 и 11. Если вам нужно собрать 15 юаней, жадный алгоритм не сработает.

Можем посчитать, по стратегии жадного алгоритма сначала вынимаем 11 самого большого номинала, а оставшиеся 4 соответствуют четырем странным монетам по 1 юаню, что для сбора 15 юаней требуется всего пять чудесных монет.

На самом деле, мы просто считаем, мы знаем, что минимальная ситуация, чтобы вынуть 3 замечательных монеты по 5 юаней, чтобы получилось 15 юаней.

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

Улучшить вычислительную стратегию

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

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

Давайте проанализируем вышеприведенную проблему, ее проблема на самом деле заключается в том, «задав набор монет номинала, сколько монет нам нужно, чтобы использовать существующую стоимость валюты, чтобы составить n».

Мы должны компенсировать это n, пока n не равно 0, в последнем всегда будет монета, и эта монета составляет n, например, мы используем{11,1,1,1,1}Давайте составим 15, мы возьмем его{11,1,1,1}, и, наконец, выводим{1}Ровно 15.

Если вы используете{5,5,5}Приходим составлять 15, последняя монета 5, гладим ее по такой задумке:

Затем предположим, что последняя монета 11, тогда осталось 4. В это время снова возникает проблема, сколько монет нам нужно, по крайней мере, чтобы вычислить n-11, в это время n = 4, мы можем только взять 4 монеты номиналом 1 валюта
Если предположить, что последняя монета равна 5, в это время снова возникает проблема, сколько монет нам нужно, чтобы составить n-5 с существующей стоимостью валюты.

Знаете ли вы, что наш вопрос может быть непрерывно разложен на «сколько монет нам нужно, чтобы компенсировать n с существующей стоимостью валюты», например, мы используем функцию f (n), чтобы представить «сколько монет нам нужно чтобы составить минимальное n".

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

В настоящее время мы соответственно предполагаем, что три номинала 1, 5 и 11 являются последними монетами:

Номинал последней монеты 11: min = f(4) + 1
Номинал последней монеты 5: min = f(10) + 1
Последняя монета имеет номинал 1: min = f(14) + 1

На данный момент нашли проблему?Хоть поменяйте min иf(4)、f(10)、f(14)Минимальное значение из трех функциональных решений актуально, ведь «+1» сзади есть у всех.

Предположим, что общее количество добытых монет равно n, тогдаf(4) = f(n-11),f(10) = f(n-5),f(14) = f(n-1), получаем следующую формулу:

f(n) = min{f(n-1), f(n-5), f(n-11)} + 1

Давайте перейдем к приведенной выше формулеf(n-1)Каково минимальное количество монет, чтобы компенсировать это, становится ли это следующей формулой:

f(n-1) = min{f(n-1-1), f(n-1-5), f(n-1-11)} + 1

И так далее...

Это действительно дежавю, не рекурсия ли это?

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

function f(n) {
    if(n === 0) return 0
    let min = Infinity
    if (n >= 1) {
        min = Math.min(f(n-1) + 1, min)
    }

    if (n >= 5) {
        min = Math.min(f(n-5) + 1, min)
    }

    if (n >= 11) {
        min = Math.min(f(n-11) + 1, min)
    }

    return min
}

console.log(f(15)) // 3

Когда n=0, вернуть 0 напрямую, чтобы повысить надежность программы.
Сначала мы устанавливаем минимальное изменение min как «бесконечное», что удобно для последующего использования.Math.minнайти минимальное значение
Когда последняя монета равна 1, мы рекурсивноmin = Math.min(f(n-1) + 1, min), найти минимальное изменение в этом случае
Когда последняя монета равна 5, мы рекурсивноmin = Math.min(f(n-5) + 1, min), найти минимальное изменение в этом случае
Когда последняя монета равна 11, мы рекурсивноmin = Math.min(f(n-11) + 1, min), найти минимальное изменение в этом случае

Недостатки рекурсии

Кажется, мы решили проблему, но не волнуйтесь, мы продолжаем тестировать, когда n=70, мы проверяем минимальное количество монет, которое нам нужно, чтобы составить это число.

Ответ 8, но наше время таково:

Что если n=270?С поддержкой процессора i7 восьмого поколения и версии node.js 12.x я так долго бегал и не мог разобраться:

При n=27000 мы успешно взорвали стек:

Так почему же так долго выполняется?В конечном счете это вызвано неэффективностью рекурсивного алгоритма.Давайте посмотрим на следующий рисунок:

Если мы вычисляем f(70), нам нужно рассчитать разные ситуации, когда последняя монета равна 1, 5 и 11, и эти три разные ситуации можно разложить на три ситуации как подзадачи и т.д. алгоритм имеет сложность O(3ⁿ), что крайне неэффективно.

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

То, что мы отметили красным, это все одинаковые функции расчета, например, есть две f(64), f(58), f(54), они повторяются, это только верхушка айсберга под всей нашей системой расчета , we Есть также много двойных вычислений, которые не могут быть показаны на рисунке.

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

Давайте возьмем простой пример. Например, мы должны рассчитать сумму «1 + 1 + 1 + 1 + 1 + 1 + 1 + 1».

Начинаем считать... пока не посчитаем сумму, рассчитанную выше, равной 8, затем прибавляем "+ 1" после вышеуказанного "1 + 1 + 1 + 1 + 1 + 1 + 1 + 1", тогда сумма сколько?

В это время вы должны не уметь считать и ляпнуть «9».

Почему наши расчеты сзади такие быстрые? Это потому, что мы уже запомнили предыдущий результат «8» в нашем мозгу, нам нужно только вычислить «8 + 1», что позволяет избежать повторения вычисления ранее рассчитанного содержания.

Как мы используем рекурсию? Продолжать считать «1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1», чтобы вычислить «9», занимает очень много времени.

Предположим, что минимальное количество монет необходимо для создания n монет номиналом m. В приведенной выше задаче рекурсивная временная сложность составляет удивительную O (nᵐ), а экспоненциальную временную сложность можно назвать одной из наихудших временных сложностей.

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

Заметка и рекурсивное

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

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

отображение кода javascript

function f(n) {
    function makeChange(amount) {
        if(amount <= 0) return 0
    
        // 校验是否已经在备忘录中存在结果,如果存在返回即可
        if(cache[amount]) return cache[amount]
    
        let min = Infinity
        if (amount >= 1) {
            min = Math.min(makeChange(amount-1) + 1, min)
        }
    
        if (amount >= 5) {
            min = Math.min(makeChange(amount-5) + 1, min)
        }
    
        if (amount >= 11) {
            min = Math.min(makeChange(amount-11) + 1, min)
        }
    
        return (cache[amount] = min)
    }
    // 备忘录
    const cache = []
    return makeChange(n)
}
console.log(f(70)) // 8

отображение java-кода

public class Cions {

    public static void main(String[] args) {
        int a = coinChange(70);
        System.out.println(a);
    }
    private static HashMap<Integer,Integer> cache = new HashMap<>();
    public static int coinChange(int amount) {
        return makeChange(amount);
    }
    public static int makeChange(int amount) {
        if (amount <= 0) return 0;

        // 校验是否已经在备忘录中存在结果,如果存在返回即可
        if(cache.get(amount) != null) return cache.get(amount);

        int min = Integer.MAX_VALUE;
        if (amount >= 1) {
            min = Math.min(makeChange(amount-1) + 1, min);
        }

        if (amount >= 5) {
            min = Math.min(makeChange(amount-5) + 1, min);
        }

        if (amount >= 11) {
            min = Math.min(makeChange(amount-11) + 1, min);
        }

        cache.put(amount, min);
        return min;

    }
}

Наше время выполнения составляет всего:

На самом деле использование memo для решения проблемы рекурсивных повторяющихся вычислений называется «memoized search».

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

Временная сложность этого рекурсивного алгоритма с memo составляет всего O(n), что не сильно отличается от временной сложности динамического программирования.

Так это не сработает? Зачем заниматься динамическим программированием?

Помните другую большую проблему с рекурсией, о которой мы упоминали выше?

Взрывной стек!

Это наш рекурсивный расчет мемоf(27000)результат:

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

Это определяется рекурсивной формой вычисления, рекурсией здесь является идея вычисления «сверху вниз», т. е. отf(70) f(69)...f(1)Постепенно разлагайтесь, эта идея здесь не в полной мере применима, нужна идея «снизу вверх» для решения задачи.

"снизу вверх" этоf(1) ... f(70) f(69)Для решения крупномасштабных задач путем рекурсии мелкомасштабных задач динамическое программирование обычно использует итерацию вместо рекурсии для решения проблем.

Идея «сверху вниз» очень распространена в идее другого алгоритма, то есть алгоритма «разделяй и властвуй».

Кроме того, еще одним недостатком рекурсии + мемо является то, что нет места для оптимизации, потому что в худшем случае максимальная глубина рекурсии равна n.

Следовательно, нам нужно, чтобы системный рекурсивный стек использовал пространство O(n), которое определяется рекурсивной формой, и нам вообще не нужно столько места для хранения после перехода на итерацию, мы можем продолжать смотреть вниз.

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

Помните, как выглядит форма каждого узла после того, как мы использовали кеш заметок выше, мы используем его как «заметку» в виде таблицы, эта таблица называется таблицей DP, как показано ниже:

Примечание: на картинке вышеf[n]Представляет функцию минимального количества монет, необходимого для составления n, а числа в квадрате представляют результат функции

Можем ли мы найти шаблон на картинке выше?

мы наблюдаемf[1]: f[1] = min(f[0], f[-5], f[-11]) + 1

из-заf[-5]Такого отрицательного числа не существует, мы все устанавливаем его на положительную бесконечность, тогдаf[1] = 1.

посмотри сноваf[5]: f[1] = min(f[4], f[0], f[-6]) + 1, который на самом деле проситf[4] = 4,f[0] = 0,f[-6]=InfinityНаименьшее значение равно 0, а в конце добавляется 1, что равно 1, тогдаf[5] = 1.

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

f[n] = min(f[n-1], f[n-5], f[n-11]) + 1

Помните, мы упоминали, что динамическое программирование имеет больше возможностей для оптимизации?Рекурсия + памятка требует O(n) пространственной сложности из-за глубины рекурсии, но динамическое программирование на основе итераций требует только сложности постоянного уровня.

Посмотрите на рисунок ниже, например, когда мы решаем f(70), нам нужны только первые три решения, а именноf(59) f(69) f(65)Применяя формулу можно получить, тогдаf(0)f(1) ... f(58)Это вообще бесполезно, мы больше не можем их хранить и занимать лишнее место, что оставляет нам пространство для оптимизации.

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

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

краевая задача

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

Разберитесь с проблемой, что n отрицательно в f[n]: Наше решение этой проблемы состоит в том, что всякий раз, когда n отрицательно, мы всегда будемf[n]Рассматривается как положительная бесконечность, потому что при нормальных обстоятельствах у нас не было бы массива с отрицательным нижним углом, поэтому на самом деле n является отрицательным числом.f[n]It does not exist at all, and because we require the least change, in order to exclude this non-existent situation and facilitate our calculation, we directly regard it as positive infinity, which can facilitate the realization of our dynamic transfer equation to the greatest степень.

Разберитесь с проблемой, что n в f[n] равно 0:n=0Ситуация относится к начальному условию уравнения динамического перехода, а начальное условие также является частным случаем, с которым уравнение динамического перехода не может справиться.Например, если у нас нет этого начального условия, наше уравнение имеет следующий вид:f[0] = min(f[-1], f[-5], f[-11]) + 1, наименьшее также является положительной бесконечностью, что является частным случаем, с которым нельзя справиться, поэтому мы можем только задать начальные условия.

Разобравшись с краевой задачей, мы можем получить полное уравнение динамического переноса:

f[0] = 0 (n=0)
f[n] = min(f[n-1], f[n-5], f[n-11]) + 1 (n>0)

Полный анализ проблемы изменений

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

Например:

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

На самом деле, вышеприведенная задача о сдаче является обобщением проблемы сдачи, с которой мы имели дело.Наши номиналы фиксированы, то есть 1, 5, 11. На этот раз это неопределенно, но дан массив монет, которые содержат связанные между собой монеты. Номинальная стоимость.

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

Определяем оптимальную подструктуру:Оптимальная подструктура состоит в том, что решение исходной задачи состоит из оптимального решения подзадачи.Мы предполагаем, что для создания общего номинала n требуется не менее k монет, тогдаf(n) = min{f(n-cᵢ)}, cᵢЭто номинал монеты.

Решение проблем с границей:Это все еще старая процедура, когда n отрицательно, значение равно положительной бесконечности, а когда n=0, значение также равно 0.

Выведите уравнение динамического переноса:

f[0] = 0 (n=0)
f[n] = min(f[n-cᵢ]) + 1 (n>0)

На основе приведенного выше вывода мы получаем следующий код:

отображение кода javascript

const coinChange = (coins, amount) => {
  // 初始化备忘录,用Infinity填满备忘录，Infinity说明该值不可以用硬币凑出来
  const dp = new Array(amount + 1).fill(Infinity)

  // 设置初始条件为 0
  dp[0] = 0

  for (var i = 1; i <= amount; i++) {
    for (const coin of coins) {
      // 根据动态转移方程求出最小值
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1)
      }
    }
  }

  // 如果 `dp[amount] === Infinity`说明没有最优解返回-1,否则返回最优解
  return dp[amount] === Infinity ? -1 : dp[amount]
}

отображение java-кода


class Solution {
    public int coinChange(int[] coins, int amount) {
        // 初始化备忘录,用amount+1填满备忘录,amount+1 表示该值不可以用硬币凑出来
        int[] dp = new int[amount + 1];
        Arrays.fill(dp,amount+1);
        // 设置初始条件为 0
        dp[0]=0;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                // 根据动态转移方程求出最小值
                if(coin <= i) {
                    dp[i]=Math.min(dp[i],dp[i-coin]+1);
                }
            }
        }
        // 如果 `dp[amount] === amount+1`说明没有最优解返回-1,否则返回最优解
        return dp[amount] == amount+1 ? -1 : dp[amount];
    }
}

резюме

Подведем итоги процесса обучения:

Начиная с жадного алгоритма для решения задачи о размене, установлено, что жадный алгоритм не может найти оптимальное решение в любой ситуации.
Мы решили изменить способ мышления, чтобы решить существующую проблему, и мы, наконец, нашли ключевой момент, а именно «оптимальную подструктуру».
С помощью двух приведенных выше выводов мы рекурсивно решаем задачу наименьшего изменения.
Однако после анализа сложности алгоритма и фактического тестирования мы обнаружили, что рекурсивный метод крайне неэффективен, и мы должны использовать метод для решения текущей задачи.
Мы решили проблему временной сложности в виде меморандума + рекурсия, но мышление сверху вниз не давало нам избавиться от тумана взрыва стека, нам требовалось новое мышление «снизу вверх».
Мы решаем эту проблему эффективно и итеративно с помощью уравнений динамического перехода

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

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

Может быть, вы зададите столько вопросов на собеседовании, какой из них использовать динамическое программирование?Как судить?

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

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

найти максимальное значение и минимальное значение
Определить, осуществим ли план
Количество статистических программ

Добро пожаловать в публичный аккаунт: