Как я объяснил динамическое программирование своей 5-летней племяннице? | Ежегодное эссе Nuggets

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

задний план

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

Однажды я спросил ее

"Сколько будет 1+1+1+1+1?"

"Поднимите мизинец и начните считать, 5!"

«Тогда как насчет добавления 1?»

"Конечно 6" - выпалил

"Почему ты так быстро на этот раз?"

"Разве сейчас не 5, плюс 1 будет 6?"

«Поэтому вам не нужно пересчитывать, потому что вы помните, что ответ был 5! Динамическое программирование заключается в следующем: запоминание того, что было раньше, экономит время».

К точке

$\color{red}{Играть весело, играть весело, не смейтесь над дп! }$

Давайте взглянем на объяснение статьи Китайской научной энциклопедии.

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

Пропустите детскую обувь, которую не видно, давайте сделаем это проще

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

Что мы видим в этом вопросе?

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

Среди них f(x) — значение первого шага, задайте начальное значение, x > 0, затем первый шаг

f(1) = 1;

f(2) = 2;

...

f(6) = 6

Что в мире программ используется для хранения структуры данных, которая может записывать предыдущее значение результата?

Очевидный:множество. Прямое использование индексов для хранения, Ба Ши, это динамика в динамическом программировании, планирование заключается в определении некоторых границ и инициализации.

перейти к тренировочному вопросу

$\color{red}{Не читайте, это тоже простой вопрос}$

leetcode 322: у вас есть три вида монет, 2 юаня, 5 юаней, 7 юаней, каждого вида монет достаточно, купить книгу нужно 27 юаней, использовать наименьшую комбинацию монет

Как вы себя чувствуете, возвращаясь к вопросам о приеме в начальную школу?

--Простой анализ: минимальная комбинация монет -> старайтесь использовать большие монеты

Кто придумал этот глупый вопрос? Это так просто

7+7+7=21, 21+2+2+2=27, 6 монет

дерьмо

7+5+5+5+5=27, 5 монет

Мы можем бурно думать об этом, считая от большего к меньшему, в сумме может получиться не более 27, например

7+7+7+7 > 27 (исключено)

7+7+7+5 или 7+7+7+2+2+2 6 шт.

....

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

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

ключевое предупреждение

1.1 Компонент динамического программирования 1: определение состояния

Проще говоря, при решении динамического программирования вам нужно открыть массив, что представляет собой каждый элемент массива f[i] или f[i][j] аналогично тому, что представляют x, y, z в математических задачах.

Решение динамического программирования требует двух знаний:

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

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

Разве я не сказал только что первый вопрос, результат вычисления последнего шага равен 5. Для этого вопроса, хотя мы не знаем, какова оптимальная стратегия, оптимальной стратегией должно быть K монет, сумма номинала a1, a2, ....ak равна 27.

Так что должна быть конечная монета: ак.

Без учета таких монет номиналы предыдущих монет в сумме составляют 27-ак.

Ключевой момент 1:

Нам все равно, как пишутся предыдущие k-1 монет 27-ak (может быть одно написание, может быть 100 написаний), и мы даже не знаем сейчас ak и K, но мы уверены, что предыдущее На монете написано 27-ак

Ключевой момент 2:

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

подзадача

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

подожди, мы до сих пор не знаем, какая последняя монета ак

Очевидно, что последняя монета может быть только 2, 5 или 7.
Если ak равно 2, f(27) должно быть f(27-2)+1 (1 представляет последнюю монету 2)
Если ak равно 5, f(27) должно быть f(27-5)+1 (1 — последняя монета 5)
Если ak равно 7, f(27) должно быть f(27-7)+1 (1 — последняя монета 7)

Поэтому используйте наименьшее количество монет = f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}

1.2 Компонент динамического программирования 2: уравнения перехода

Пусть состояние f(x) = минимальное количество монет для записи x

Для любого x: f(X) = min{f(X-2)+1, f(X-5)+1, f(X-7)+1}

1.3 Компонент динамического программирования 2: начальные условия и граничные случаи

Задайте вопрос

Что, если х-2, х-5, х-7 меньше 0?
Когда ты остановишься?

1.3.1

Если Y нельзя указать, определите f[Y] = положительная бесконечность

Например, f[-1], f[-2] = положительная бесконечность

Например: нельзя записать f[1]=min{f(-1)+1, f(-3)+1, f(-6)+1}

Начальное условие: f[0] = 0

2.4 Компонент динамического программирования 2: Порядок вычислений

Вычисление: f[1], f[2], ... f[27]

Когда мы вычисляем f[x], f[x-2], f[x-5], f[x-7], мы получаем результат

Как показано на рисунке:

f[x] = минимальное количество монет для написания x

f[x] = ∞ означает, что x не может быть записан монетами

Код ссылки

public  static  int coinChange(int [] A, int M ) {
 int[] f = new int[M+1];
 int n = A.length;
 f[0] = 0;
 int i,j;
 for (i = 1; i<=M; i++) {
    f[i] = Integer.MAX_VALUE;
    for (j = 0; j< n;j++) {
        // 边界条件判断
        if (i >= A[j] && f[i - A[j]] != Integer.MAX_VALUE) {
            f[i] = Math.min(f[i - A[j]] + 1, f[i]);
          //  System.out.println(i + "=" +f[i]);
        }
    }
 }
 if (f[M] == Integer.MAX_VALUE) {
    f[M] = -1 ;
 }
 return  f[M];
}

😄

$\color{red}{Код ядра всего 4 строки, это очень просто~}$

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

Еще вопрос по обучению

Давайте возьмем другой вопрос, один вопрос слишком случайный~

leetcode 62 : разные пути

Робот расположен в верхнем левом углу сетки m x n (начальная точка отмечена как «Старт» на изображении ниже).

Робот может двигаться вниз или вправо только на один шаг за раз. Робот пытается достичь правого нижнего угла сетки (помеченного «Готово» на изображении ниже).

В. Сколько всего существует различных путей?

Прочитав приведенные выше шаги по решению проблемы, шаг за шагом

2.1 Компонент динамического программирования 1: определение состояния

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

Неважно, как робот доберется до правого нижнего угла, всегда остается последний ход: - вправо или вниз

Если показано, мы устанавливаем координаты нижнего правого угла как (m-1,n-1)

Тогда позиция робота на предыдущем шаге последнего шага будет (m-2, n-1) или (m-1, n-2)

подзадача

Тогда, если у робота есть x способов пройти из левого верхнего угла в (m-2,n-1) и Y способов пройти из левого верхнего угла в (m-1,n-2), то робот имеет X+Y путей к (m-1,n-1)

Вопрос превращается в то, сколько способов робот может пройти из верхнего левого угла в (m-2,n-1) или (m-1,m-2)

Если вы перейдете к (m-2,n-1), как показано на рисунке:

Мы можем просто убить последнюю колонку

Точно так же, если вы переходите на строку (m-1, n-2), уменьшите одну строку.

государство:

Пусть f[i][j] будет количеством способов, которыми робот может пройти из левого верхнего угла в (i,j)

2.2 Компонент динамического программирования 2: уравнения перехода

Для любой сетки:

f[i][j] = f[i-1][j] + f[i][j-1]

1 2 3

1 показывает, сколько путей робот может пройти до [i][j]

2 показывает, сколько способов робот может пройти до f[i-1][j]

3 показывает, сколько способов робот может пройти до f[i][j-1]

2.3 Компонент динамического программирования 3: начальные условия и граничные случаи

Начальное условие: f[0][0]=1, так как у робота есть только один путь в левый верхний угол

Граничная ситуация: i=0 или j=0, тогда предыдущий шаг может идти только в одном направлении, то есть в 0-й строке или 0-м столбце, для каждого шага есть только один случай, тогда f[i][ j] = 1, все остальные области удовлетворяют уравнению перехода.

3.4 Компонент динамического программирования 4: Порядок вычислений

Считать по ряду, зачем считать по ряду?

Для этого вопроса, когда f[1][1] вычисляется по строке, были вычислены как f[0][1], так и f[1][0], а две координаты также вычисляются по столбцу. надо заново считать.

f[0][0] = 1
Вычислить 0-ю строку: f [0] [0], F [0] [1], ..., f [0] [N-1]
Вычислить строку 1: f[1][0],f[1][1],...,f[1][n-1]
...
Вычислить строку m-1: f[m-1][0],f[m-1][1],...,f[m-1][n-1]

Временная сложность: O(mn)

Код ссылки

public int uniquePaths(int m, int n) {
    int[][] f = new int[m][n];
    int i,j;
    for (i = 0; i<m; i++) {
        for (j = 0; j< n; j++) {
            if (i == 0 || j == 0) {
                f[i][j] = 1;
            } else {
                f[i][j] = f[i -1][j] + f[i][j-1];
            }
        }
    }
    return f[m-1][n-1];
}

в заключении

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

1. Считать

Сколько способов попасть в правый нижний угол
Сколькими способами можно выбрать k чисел да и сложить

2. Найдите максимальное и минимальное значения

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

3. Ищите существования

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

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

Популярная рекомендация:

- Какие? Вы не пробовали OAuth2, который используют github, Alipay и WeChat?

- Вы говорите, что граница дихотомии слишком сложна, чтобы забить вас до смерти

- JAVA использует один и тот же IP-адрес для доступа к одному и тому же интерфейсу для ограничения частоты (распределенный (распределенный бизнес JD.com) и сценарии реального боевого использования корзины токенов.

- Анализ длинных слов Wanwen: если вы хотите попасть на большую фабрику, вам нужно освоить основы кеша ЦП.

В конце статьи мы недавно составили материал для интервью «Руководство по прохождению интервью по Java», в котором рассматриваются основные технологии Java, JVM, параллелизм Java, SSM, микросервисы, базы данных, структуры данных и многое другое. способ получения:GitHub GitHub.com/ting с -note…, больше контента, обратите внимание на мои наггетсы и предлагайте их один за другим.