В процессе изучения «Структур данных и алгоритмов», поскольку люди привыкли к прямолинейному мышлению, «рекурсию» и «динамическое программирование» с концепциями циклов (обход) часто относительно трудно понять.
Программист Сяо Ву намерен использовать форму анимации, чтобы помочь понять «рекурсию», а затем расширить концепцию «рекурсии», чтобы понять идею алгоритма «динамического программирования».
что такое рекурсия
Сначала определите:Рекурсивный алгоритм — это алгоритм, который прямо или косвенно вызывает собственную функцию или метод.
С точки зрения непрофессионала, суть рекурсивного алгоритма состоит в том, чтобы разложить проблему на подзадачи того же типа проблемы с уменьшенным масштабом, а затем рекурсивно вызвать метод для выражения решения проблемы. Он имеет следующие характеристики:
Решение проблемы можно разложить на решения нескольких подзадач.
Эта задача точно такая же, как подзадача после декомпозиции, за исключением того, что масштаб данных другой.
Существует рекурсивное условие завершения, то есть должно быть четкое условие рекурсивного завершения, которое называется рекурсивным выходом.
Анализ выполняется с помощью анимации по одной функции за раз.
1. Решение проблемы можно разложить на решения нескольких подзадач
Подзадача — это проблема с меньшим объемом данных, чем проблема, которая ей предшествует.
В анимации вопрос ① (большая область) разделен на вопрос ②, а вопрос ② состоит из двух подзадач (две средние области).
2. Эта задача точно такая же, как подзадача после декомпозиции, за исключением того, что масштаб данных другой.
Логика «число ① делится на число ②» и «число ② делится на число ③» одинакова, и идея решения та же.
3. Есть рекурсивное условие завершения, то есть есть рекурсивный выход
Задача разбивается на подзадачи, подзадачи разбиваются на подподзадачи, слой за слоем, бесконечного цикла быть не может, что требует условий завершения.
①Число делится на ②Число, ②Число делится на ③Число, ③Число делится на ④Число, и каждая область имеет только одну проблему, которую нельзя разделить при делении на ④Число, что указывает на наличие рекурсивного условия завершения.
Начните с классического примера рекурсии
1. Суммирование массива
Sum(arr[0...n-1]) = arr[0] + Sum(arr[1...n-1])
Последняя функция Sum решает ту же задачу, но меньшую, чем предыдущая Sum.
Sum(arr[1...n-1]) = arr[1] + Sum(arr[2...n-1])
И так далее, пока сумма пустого массива не станет равна 0. В этот момент это становится самой основной проблемой.
Sum(arr[n-1...n-1] ) = arr[n-1] + Sum([])
Задача о Ханойской башне.
Задача о ханойской башне также является классической рекурсивной задачей, которая описывается следующим образом:
Задача Ханойской башни: В древности здесь была буддийская пагода.В башне было три блока А,В и С.На блоке А было 64 плиты.Плиты были разного размера. Есть монах, который хочет переместить эту тарелку с места А на место Б, но за раз разрешается перемещать только одну тарелку, и во время процесса перемещения тарелки на трех сиденьях всегда удерживают большую тарелку внизу. и маленькая тарелка сверху.
① Если есть только 1 тарелка, вам не нужно использовать башню B, просто переместите тарелку напрямую из A в C.
② Если есть 2 тарелки, вы можете сначала переместить тарелку 1 на тарелку 2 в B, переместить тарелку 2 в C, переместить тарелку 1 в C. Это объясняет: вы можете переместить 2 диска из A в C с помощью B, и, конечно же, вы также можете переместить 2 диска из A в B с помощью C.
③ Если есть 3 тарелки, то по заключению 2-х тарелок можно с помощью C переместить две тарелки на тарелке 3 из A в B; переместить тарелку 3 из A в C, A становится свободным местом; с помощью сиденья A, переместите две пластины с B на C.
④ По аналогии вышеприведенная идея может быть распространена на случай n пластин, и меньшие n-1 пластины рассматриваются как единое целое, что и является требуемой подзадачей.В качестве примера мы можем использовать башню B. Пустая башня B переместит n-1 дисков над диском A из A в B; переместите самый большой диск A в C, A станет пустой башней; с помощью пустой башни A переместите n-2 диска на башню B в A , переместите самую большую пластину C в C, и B станет пустой башней. . .
3. Проблема подъема по лестнице
Описание проблемы:
Человек может подняться только на 1 или 2 ступени за раз. Предположим, что ступенек n, сколькими способами этот человек может подняться по лестнице?
Начнем с простого, в качестве примера возьмем 4 ступени, вы можете подняться по лестнице, поднимаясь по 1 ступени за раз:
Вы можете подняться по лестнице, поднявшись сначала на 2 ступени, а затем на 1 ступень за раз.
Здесь вы можете подумать об этом: вы можете разделить все ходы на две категории в соответствии с первым ходом:
① Первая категория – это первый шаг к тому, чтобы сделать шаг
② Вторая категория — это первый шаг, чтобы сделать 2 шага.
Таким образом, способ прохождения n шагов равен способу прохождения сначала 1-го шага, затем n-1 шагов, а затем добавления способа прохождения сначала 2 шагов, затем n-2 шагов.
Формула:
f(n) = f(n-1)+f(n-2)
С формулой рекурсии рекурсивный код в основном сделан наполовину. Затем рассмотрим условие рекурсивного завершения.
Когда есть шаг, нам не нужно продолжать рекурсию, есть только один путь.
такf(1)=1.
используяn = 2,n = 3После экспериментов с таким относительно небольшим числом оказалось, что этого рекурсивного условия завершения недостаточно.
n = 2час,f(2) = f(1) + f(0). Если есть только одно рекурсивное условие завершенияf(1) = 1,Тотf(2)Ее нельзя решить, и рекурсия не может закончиться. Итак, кромеf(1) = 1В дополнение к этому рекурсивному условию завершения существуют такжеf(0) = 1, что указывает на то, что есть способ пройти 0 шагов, что кажется немного нелогичным с точки зрения мышления и анимации. Итак, для простоты понимания пустьf(2) = 2В качестве условия прекращения это означает пройти 2 шага, есть два способа пройти, один шаг или два шага.
Обобщенно следующим образом:
① Если предположить, что есть только одна ступенька, то есть только один путь — подняться на одну ступеньку.
② Предположим, что есть два шага, тогда есть два способа пройти, один шаг или два шага.
По рекурсивному условию:
f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2)
Легко получить рекурсивный код:
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}
С помощью трех приведенных выше примеров подведите итог тому, как писать рекурсивный код:
1. Найдите правила, как разбивать большие проблемы на более мелкие
2. Пишите формулы рекурсии по правилам
3. Вывести условие завершения через критическую точку рекурсивной формулы
4. Преобразовать формулы рекурсии и условия завершения в код
Что такое динамическое программирование
Прежде чем знакомиться с динамическим программированием, давайте представим стратегию «разделяй и властвуй» (Divide and Conquer).
разделяй и властвуй стратегия
Разложите исходную проблему на несколько более мелких подзадач, подобных исходной проблеме (Divide), решить эти подзадачи «рекурсивно» (Conquer), а затем объединить решения этих подзадач, чтобы построить решение исходной задачи.
Потому что при решении больших задач необходимо рекурсивно искать мелкие проблемы, поэтому он вообще реализуется «рекурсивным» методом, то есть сверху вниз.
Динамическое программирование
По сути, динамическое программирование похоже на стратегию «разделяй и властвуй»: оно также разбивает исходную проблему на несколько более мелких подзадач, рекурсивно решает эти подзадачи, а затем объединяет решения подзадач для получения решения задачи. оригинальная проблема. Разница в том, что эти подзадачи будут перекрываться.После того, как подзадача решена, она может быть решена снова, поэтому мы думаем об объединении подзадач этих подзадач.раствор и хранить, когда вы снова будете решать эту подзадачу в следующий раз, просто решите ее прямо. Фактически это означает, что задача, решаемая с помощью динамического программирования, является подмножеством задачи, решаемой с помощью стратегии «разделяй и властвуй», но это подмножество больше подходит для решения с помощью динамического программирования для получения меньшего времени выполнения. То есть проблема, которую можно решить с помощью динамического программирования, может быть решена стратегией «разделяй и властвуй», но время выполнения будет большим.. Поэтому стратегии «разделяй и властвуй» обычно используются для решения проблем, в которых подзадачи противопоставлены друг другу, что называется стандартным «разделяй и властвуй», тогда как динамическое программирование используется для решения проблем с перекрывающимися подзадачами.
Понятия «стратегия разделяй и властвуй» и «динамическое программирование» также близки к «жадному алгоритму» и «алгоритму возврата». Из-за нехватки места программист Сяо Ву не будет здесь его расширять, а введет «жадный алгоритм» в подробности в следующих статьях. Алгоритмы", "Алгоритмы возврата", "Алгоритмы разделяй и властвуй", обратите внимание :)
Ключевые моменты концепции «динамического программирования» извлекаются и описываются следующим образом:
1. Динамическое программирование пытается решить каждую подзадачу только один раз.
2. Как только решение данной подзадачи вычислено, оно сохраняется в памяти, так что в следующий раз, когда потребуется решение той же подзадачи, можно будет напрямую просмотреть таблицу.
От рекурсии к динамическому программированию
или сподниматься по ступенькамНапример, если он решается рекурсивным способом, то временная сложность этого метода составляет O(2^n). Конкретные расчеты см. в предыдущей статье автора "Песнь Льда и Пламени: временная сложность и Космическая сложность "".
Тот же цвет представляет собой повторяющуюся часть задачи о подъеме по ступенькам в процессе рекурсивного вычисления.
Явление можно найти по картинке.Выполняем рекурсивные операции сверху вниз, например:f(n)даf(n-1)иf(n-2)добавить,f(n-1)даf(n-2)иf(n-3)добавить.
Подумайте об этом: что произойдет, если вывод будет выполняться восходящим, итеративным способом?
В следующей таблице поясняетсяf(n)Процесс решения снизу вверх.
количество шагов
1
2
3
4
5
6
7
8
9
количество ходов
1
2
Первая строка таблицы представляет количество ступеней лестницы, а вторая строка представляет количество ступеней, соответствующих нескольким ступеням.
вf(1) = 1иf(2) = 2явный результат выше.
Первая итерация, если количество шагов равно 3, то количество ходов равно 3, черезf(3) = f(2) + f(1)приходить.
количество шагов
1
2
3
4
5
6
7
8
9
количество ходов
1
2
3
Во второй итерации, если количество шагов равно 4, то количество ходов равно 5, черезf(4) = f(3) + f(2)приходить.
количество шагов
1
2
3
4
5
6
7
8
9
количество ходов
1
2
3
5
Видно, что в каждом итерационном процессе необходимо сохранять только два предыдущих состояния, а новое состояние можно вытеснить.
show me the code
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
// a 保存倒数第二个子状态数据，b 保存倒数第一个子状态数据， temp 保存当前状态的数据
int a = 1, b = 2;
int temp = a + b;
for (int i = 3; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return temp;
}
программа изi = 3начать повторять до тех пор, покаi = nЗаканчивать. На каждой итерации подсчитывается количество ходов на один шаг дальше. Во время итерации необходимо сохранить только две временные переменные a и b, которые представляют результаты предыдущей и предыдущей итераций соответственно. Для простоты понимания введена переменная temp. temp представляет значение результата текущей итерации.
На первый взгляд видно, что на самом деле кода добавлено не так много, а просто оптимизировано, временная сложность снижена до O(n), а пространственная сложность также уменьшена до O(1), т.е. Сила динамического программирования!
Подробно объясните динамическое программирование.
В «динамическом программировании» есть три важных понятия:
«Задача подъема по ступеням» — относительно простая задача в динамическом программировании, потому что она имеет только одно измерение изменения, а если задействовано несколько измерений, проблема становится намного сложнее.
Сложность заключается в том, чтобы найти эти три понятия в «динамическом программировании».
Например, «Король и проблема золотого рудника».
Король и проблема золотого рудника
В одной стране было обнаружено 5 золотых приисков, каждый с разным золотым запасом и разным количеством рабочих, необходимых для раскопок. Общее количество задействованных горнорабочих составляет 10 человек. Каждый золотой рудник либо полностью добыт, либо не добыт, и половину людей нельзя отправить на добычу половины золота. Попросите программу решить, чтобы получить как можно больше золота, какие золотые прииски выбрать для добычи?
Найдите эти три концепции в динамическом программировании.
[Оптимальная подструктура] в задаче о короле и золотом руднике
В задаче о короле и золотом руднике есть две [оптимальные подструктуры]:
① 4 Gold Mine 10 Лучший выбор для рабочих
② 4 Gold Mine (10 - 5) Лучший выбор для рабочих
4 Соотношение между оптимальным выбором золотой руды и 5 оптимальным выбором золотой руды
В задаче о короле и золотом руднике есть две [границы]:
① Когда есть только один золотой рудник, вы можете добывать только этот единственный золотой рудник, а количество полученного золота равно количеству золотого рудника.
② Когда заданного количества рабочих недостаточно, чтобы выкопать золотую жилу, количество полученного золота равно 0.
[Формула перехода состояния] в проблеме короля и золотого рудника
Мы задаем количество золотых приисков как N, количество рабочих как W, количество золота на золотых приисках как массив G[], количество труда на золотых приисках как массив P[] и получаем [формулу перехода состояния]:
Давайте сначала разберемся, как «рабочие» и «золотые прииски» сопоставляются с помощью нескольких анимаций.
1. Добывать только первый золотой рудник
На первом золотом руднике доход от добычи двумя рабочими равен нулю.Когда есть трое рабочих, доход составляет 200. После этого, даже если добавить больше рабочих, доход останется прежним, потому что может быть только один золотой рудник. заминировано.
2. Выкопайте первую и вторую золотые шахты.
В случае первого и второго золотых рудников доход от добычи первых двух рабочих равен нулю, поскольку W
Когда есть трое рабочих, они добывают первую золотую жилу, которая начинает приносить прибыль в размере 200.
Когда есть четыре рабочих, место добычи меняется, и организуется добыча второго золотого рудника, который начинает приносить прибыль в размере 300.
Когда есть пять или шесть рабочих, выплата по-прежнему составляет 300, потому что более четырех рабочих недостаточно, чтобы вырыть первую шахту.
Когда есть семь рабочих, первый и второй золотые рудники можно добывать одновременно, начиная с выхода 500.
3. Выкопайте первые три золотых рудника
Это одна из самых важных анимаций в выпуске "Король и золотой рудник", вы можете смотреть ее несколько раз.
4. Выкопайте первые четыре золотых рудника
Это одна из самых важных анимаций в выпуске "Король и золотой рудник", вы можете смотреть ее несколько раз.
[Закон] в книге «Король и проблема золотого рудника»
Внимательное наблюдение за вышеуказанными группами анимаций можно найти:
Сравнивая «рытье первого и второго золотых приисков» и «рытье первых трех золотых приисков», в «рытье первых трех золотых приисков» доход от добычи 3 золотых приисков и 7 рабочих получается из 2 золотых приисков и 7. Результат рабочие и 2 золотых прииска и 4 рабочих, Макс(500 300 + 350) = 650;
Сравнивая «рытье первых трех золотых приисков» и «рытье первых четырех золотых приисков», в «рытье первых четырех золотых приисков» доход от добычи 4 золотых приисков и 10 рабочих получается из 3 золотых приисков, 10 рабочих и 3 золотых. мин 5 Рабочий результат, Max(850,400 + 300) = 850;
[Код динамического программирования] в проблеме короля и золотого рудника
Я надеюсь, что благодаря этой статье каждый сможет получить определенное представление о «рекурсии» и «динамическом программировании». В последующем мы изучим более сложные алгоритмические задачи, такие как алгоритм множественных рюкзаков и алгоритм Дейка Теслы, основанный на «динамическом программировании». В то же время в главе «разделяй и алгоритм покорения». Программист Сяо Ву, следите за обновлениями :)