Эта страница предлагает несколько исправленных упражнений по алгоритмам, в частности, для понимания разницы между парадигмой «разделяй и властвуй» (Разделяй и властвуй) и динамическое программирование. Специфика Найти путь (кратчайший путь), задача планирование, задача о максимальном потоке и, в более общем смысле, теория графов рассматривается отдельно.
Упражнение 1
Алгоритм грубой силы тривиален: цикл.
На каждом уровне l полное бинарное дерево состоит из 2^(l-1) листьев. Таким образом, сумма вершин равна 2 ^ l -1. Пусть l будет уровнем дерева, поэтому l=sup(log_2 (n)).
Упражнение 2
Предположим, ваш входной массив называется A. Что вам нужно сделать, так это сформировать другой массив, скажем B, каждое значение i которого вычисляется с использованием рекурсивной формулы max(A[i], B[i- 1]+A[i ])
Что вы на самом деле делаете, так это расширяете предыдущее окно или запускаете новое. Вы можете сделать это, так как вы должны выбирать только непрерывные элементы как часть ваших подмножеств.
5, -6, 7, 12, -3, 0, -11, -6
Ответ будет 19 (из подмассива {7,12})
Упражнение 3
Используйте самую длинную общую подстроку для: BDCABA и ABCBDAB. Алгоритм описывается следующим образом:
Упражнение 4
Сопоставьте самую длинную общую подстроку с самой длинной общей подпоследовательностью: BDCABA и ABCBDAB. Проблема самой длинной общей подпоследовательности (LCS) состоит в том, чтобы найти самую длинную общую подпоследовательность из всех последовательностей в наборе последовательностей (часто только двух последовательностей).
Это отличается от обычных задач поиска подстрок: в отличие от подстрок, подпоследовательности не обязаны занимать последовательные позиции в исходных последовательностях.
Упражнение 5
Расстояние Левенштейна — это строковая метрика для измерения разницы между двумя последовательностями. Неформально расстояние Левенштейна между двумя словами — это минимальное количество односимвольных модификаций (то есть вставок, удалений или замен), необходимых для замены одного слова другим. Предложите динамическую программу для решения этой задачи. Суд над МЕЙЛЕШТЕЙНОМ и ЛЕВЕШТЕЙНОМ.
Упражнение 6
Алиса и Боб по очереди играют в игру, причем Алиса начинает первой.
Изначально на доске стоит число n. В свой ход каждый игрок делает ход, состоящий из:
Выберите любой x с 0 < x < n и n % x == 0.
Замените число n на доске на n – x.
Кроме того, если игрок не может двигаться, он проигрывает игру.
Возвращает true тогда и только тогда, когда Алиса выигрывает игру, предполагая, что оба игрока играют оптимально.
Пример 1:
Вход: n = 2
Вывод: правда
Объяснение: Алиса выбирает 1, и у Боба больше нет ходов.
Пример 2:
Вход: n = 3
Вывод: ложь
Объяснение: Алиса выбирает 1, Боб выбирает 1, и у Алисы больше нет ходов.
Чтобы ответить на эту проблему, мы построим таблицу решений. dp[i] указывает результат игры для данного числа i и для игрока, начавшего игру. Алиса перепробует все факторы и выберет тот, который дает ее противнику проигрышную ценность.
Также возможно решить эту проблему более классическим рекурсивным способом, называемым сверху вниз.
И для более практической стороны мы собираемся добавить запоминание.
Упражнение 7
Вам дан массив стоимостей из целых чисел, где cost[i] — это стоимость i-й ступени лестницы. После того, как вы заплатили стоимость, вы можете подняться на одну или две ступеньки.
Вы можете начать либо с шага с индексом 0, либо с шага с индексом 1.
Верните минимальную стоимость, чтобы достичь вершины этажа.
Пример 1:
Вход: стоимость = [10,15,20]
Выход: 15
Объяснение: Вы начнете с индекса 1.
- Заплатите 15 и поднимитесь на две ступеньки, чтобы добраться до вершины.
Общая стоимость 15т.
Пример 2:
Вход: стоимость = [1,100,1,1,1,100,1,1,100,1]
Выход: 6
Объяснение: Вы начнете с индекса 0.
- Заплатите 1 и поднимитесь на две ступеньки, чтобы добраться до подсказки 2.
- Заплатите 1 и поднимитесь на две ступеньки, чтобы добраться до подсказки 4.
- Заплатите 1 и поднимитесь на две ступеньки вверх, чтобы добраться до подсказки 6.
- Заплатите 1 и поднимитесь на один шаг, чтобы добраться до подсказки 7.
- Заплатите 1 и поднимитесь на две ступеньки вверх, чтобы добраться до подсказки 9.
- Заплатите 1 и поднимитесь на ступеньку, чтобы достичь вершины.
Общая стоимость 6.
Для первого проекта мы решим эту проблему, рекурсивный. Для этого мы учитываем наименьшую стоимость, считая, что мы возвращаемся на один шаг и два шага назад. И так до тех пор, пока у вас не будет стоимости первого или второго шага.
минимальная стоимость (0) = стоимость [0]минимальная стоимость (1) = стоимость [1]
минимальная стоимость (i) = стоимость [i] + минимальная стоимость (i-1), минимальная стоимость (i-2))
Что дает следующий код:
На втором этапе мы остановимся на нисходящем подходе и добавим систему запоминания. Таким образом, уже найденный minCost не будет пересчитываться позже.
Наконец, мы рассмотрим проблему снизу вверх для динамического программирования;
Упражнение 8
Алиса и Боб играют в игру с грудами камней. В ряд выстроено четное количество стопок, и в каждой стопке положительное целое число стопок камней[i].
Цель игры состоит в том, чтобы закончить с наибольшим количеством камней. Общее количество камней во всех стопках нечетное, поэтому ничьей не бывает.
Алиса и Боб ходят по очереди, Алиса начинает первой. Каждый ход игрок берет всю стопку камней либо с начала, либо с конца ряда. Это продолжается до тех пор, пока стопки не закончатся, и в этот момент побеждает тот, у кого больше камней.
Предполагая, что Алиса и Боб играют оптимально, вернуть true, если Алиса выигрывает игру, или false, если выигрывает Боб.
Вход: камни = [5,3,4,5]
Вывод: правда
Алиса начинает первой и может взять только первые 5 или последние 5.
Допустим, она берет первые 5, поэтому строка становится [3, 4, 5].
Если Боб возьмет 3, то на доске [4, 5], и Алиса возьмет 5, чтобы выиграть с 10 очками.
Если Боб возьмет последние 5, то на доске [3, 4], и Алиса возьмет 4, чтобы выиграть с 9 очками.
Это продемонстрировало, что попадание в топ-5 было выигрышным ходом для Алисы, поэтому мы возвращаем true.
Начнем с нисходящего подхода с мемоизацией.
- Обратите внимание, что оба игрока играют оптимально, поэтому мы играем оптимально независимо от того, кто Алиса, кто Боб.
- Пусть dp(left, right) возвращает [firstScore, secondScore], где firstScore — это максимальное количество очков, когда игрок1 играет первым, secondScore — это максимальное количество очков, когда игрок2 играет вторым, он собирает камни в стопки[слева]…кучки[справа].
- Для камней в кучах[слева]…кучках[справа] игрок 1 может выбрать 2 варианта:
- Выберите слева: pickLeft = dp (слева + 1, справа).
- Счет Player1 = stacks[left] + оценка второго выбора pickLeft, поэтому firstScore = stacks[left] + pickLeft[1]
- Счет Player2 = счет первого выбора pickLeft, поэтому secondScore = pickLeft[0]
- Выбор справа: pickRight = dp(left, right – 1).
- Счет Player1 = stacks[right] + второй счет pickRight, поэтому firstScore = stacks[right] + pickRight[1]
- Счет Player2 = счет первого выбора pickRight, таким образом, secondScore = pickRight[0].
- Выберите слева: pickLeft = dp (слева + 1, справа).
- Нам нужно получить максимальное количество очков, когда игрок 1 играет первым из более чем 2 вариантов.
- Наконец, dp(0, len(stacks) – 1) возвращает [firstScore, secondScore], где alexScore = firstScore, поскольку Алиса играет первой, leeScore = secondScore, поскольку Боб играет вторым.
Теперь мы собираемся сделать восходящий алгоритм, сохранив при этом мемоизацию. Таким образом, алгоритм будет в динамическом программировании.
Упражнение 9
В очереди стоят солдаты. Каждому солдату присваивается уникальное значение ранга.
Среди них необходимо сформировать команду из 3 солдат по следующим правилам:
Выберите 3 солдат с индексом (i,j,k) и рейтингом (рейтинг[i],рейтинг[j],рейтинг[k]).
Команда действительна, если: (рейтинг[i] < рейтинг[j] <рейтинг[k]) или (рейтинг[i] > рейтинг[j] > рейтинг[k]), где (0 <= i <j <k < нет).
Верните количество команд, которые вы можете сформировать при данных условиях. (солдаты могут входить в состав нескольких команд).
Пример 1:
Вход: оценка = [2,5,3,4,1]
Выход: 3
Пояснение: В зависимости от условий можно сформировать три команды. (2,3,4), (5,4,1), (5,3,1).
Пример 2:
Вход: оценка = [2,1,3]
Выход: 0
Объяснение: Мы не можем сформировать команду в данных условиях.
Легко сделать жадный алгоритм. Последнее находится в O (n ^ 3), поэтому мы постараемся улучшить сложность с динамическим программированием.
Вот основная идея в версии динамического программирования:
Во-первых, мы вычисляем этот случай score[i] > score[j] > score[k] при условии, что i > j > k. Затем вычислите случай score[i] < score[j] < score[k].
Установите dp[i]: сколько элементов в нотации от 0 до i-1 меньше, чем в нотации[i].
Каждый раз, когда мы находим примечание[i] > примечание[j], мы накапливаем dp[j]. Здесь dp[j] означает, сколько существует notes[k] от 0 до j-1. То есть, сколько случаев удовлетворяет требованиям класса [i] > класса [j] > класса [k].
Упражнение 10
Вам дан ценовой график, где цена[i] — это цена данной акции на i-й день, а целочисленная комиссия представляет комиссию за транзакцию.
Найдите максимальную прибыль, которую вы можете получить. Вы можете совершать столько транзакций, сколько хотите, но вы должны платить комиссию за транзакцию за каждую транзакцию.
Примечание. Вы не можете совершать несколько сделок одновременно (т. е. вы должны продать акции, прежде чем покупать их снова).
Вход: цена = [1,3,2,8,4,9], комиссия = 2
Выход: 8
Объяснение: Максимальная прибыль может быть достигнута за счет:
- Купить по цене [0] = 1
– Продать по ценам[3] = 8
– Купить по ценам [4] = 4
– Продать по ценам[5] = 9
Общая прибыль равна ((8 – 1) – 2) + ((9 – 4) – 2) = 8.
Начнем сначала с нисходящего подхода.
- Пусть dp(i, canBuy) будет максимальной прибылью, которую мы можем получить от цены[i..n-1] с флагом canBuy == True означает, что мы можем купить в i-й день.
- На i-й день у нас есть 2 варианта:
- Не обращайте внимания: прибыль = dp(i+1)
- Купить или продать
- При покупке: прибыль = dp(i+1) – цена[i]
- При продаже: прибыль = dp(i+1) + цена[i] – комиссия
Мы перейдем к восходящему подходу для более традиционного динамического программирования.
Пусть dp[i][j] будет максимальной прибылью, которую мы можем получить от цены[i..n-1] с флагом j == 1, что означает, что мы можем купить в i-й день.
Поскольку наш dp имеет доступ только к 2 состояниям: текущее состояние dp dp, предыдущее состояние dp dpPrev. Мы можем оптимизировать до O(1) пространственной сложности.
Упражнение 11
Вы запланировали поездку на поезде за год вперед. Дни в году, в которые вы будете путешествовать, даны как целое число дней. Каждый день представляет собой целое число от 1 до 365.
Билеты на поезд продаются тремя способами:
абонемент на 1 день продается по цене [0] долларов,
7-дневный пропуск продается по цене [1] долларов, и
30-дневный пропуск продается по цене [2] долларов.
Абонементы позволяют путешествовать столько дней подряд.
Например, если мы получаем 7-дневный проездной на 2-й день, мы можем путешествовать 7 дней: 2, 3, 4, 5, 6, 7 и 8.
Верните минимальное количество долларов, которое вам нужно, чтобы путешествовать каждый день в заданном списке дней.
Ввод: дни = [1,4,6,7,8,20], затраты = [2,7,15]
Выход: 11
Например, вот способ купить проездные, которые позволяют вам путешествовать в соответствии с вашим планом поездки:
В первый день вы приобрели однодневный пропуск по цене [0] = 2 $, который покрывает первый день.
В день 3 вы приобрели 7-дневный абонемент по цене[1] = 7 $, который покрывает дни 3, 4, …, 9.
На 20-й день вы приобрели дневной абонемент за cost[0] = 2 $, который покрывает 20-й день.
Всего вы потратили 11 $ и покрыли все дни поездки.
Мы увидим здесь восходящий подход, потому что рассуждения очень похожи на проблему рюкзак (рюкзак) в построении раствора.
dp[i] означает до го дня минимальную стоимость билетов. Размер массива dp зависит от последнего дня поездки, поэтому нам не нужна длина массива 365.
Нам нужен логический массив для обозначения дней в пути, причина в том, что если это не день в пути, нам не нужен билет. Однако, если это день в пути, мы рассматриваем три сценария (с тремя типами билетов):
Если билет на 1 день в день i, dp[i] = dp[i – 1] + cost[0]
Если 7-дневный билет заканчивается в день i, dp[i] = min(dp[i – 7], dp[i – 6] … dp[i – 1]) + cost[1]
Если 30-дневный билет заканчивается в день i, dp[i] = min(dp[i – 30], dp[i – 29] … dp[i – 1]) + стоимость[2]
Но поскольку значение массива dp увеличивается, поэтому:
Для 7-дневного билета, заканчивающегося в день i, dp[i] = dp[i – 7] + cost[1].
Для 30-дневного билета, заканчивающегося в день i, dp[i] = dp[i – 30] + cost[2].
Упражнение 12
Вам дан массив целочисленных значений, где values[i] представляет значение i-го туристического объекта. Между двумя туристическими объектами i и j расстояние j – i.
Оценка пары (i < j) туристических объектов равна values[i] + values[j] + i – j: сумма значений туристических объектов минус расстояние между ними.
Возвращает максимальный балл пары прицелов.
Вход: значения = [8,1,5,2,6]
Выход: 11
Имеем i = 0, j = 2, values[i] + values[j] + i – j = 8 + 5 + 0 – 2 = 11
Предположим, мы выбрали сайт [i,…j]. Оценка может быть разбита на 2 части.
Первая часть — это startGain, который вы зарабатываете, начиная с определенной точки i. Обратите внимание, что startGain[i] = a[i] + i.
Вторая часть — это endGain, сумма, которую вы заработаете, финишировав в определенной точке j. Обратите внимание, что endGain[i] = a[j] – j.
Обратите внимание, что endGain может быть отрицательным.
Общий выигрыш для [i,…j] есть не что иное, как startGain[i] + endGain[j]. (Это легко проверить по определениям).
Мы должны максимизировать общий выигрыш.
С каких позиций можно начать путешествие? Понятно, что запустить можно все, кроме последнего элемента. Таким образом, оптимальное путешествие должно начинаться с одного из этих элементов.
Предположим, нам разрешено начать путешествие только в точке i. Какую максимальную сумму мы можем выиграть в этом случае? Что ж, поскольку startGain фиксирован, нам нужно максимизировать endGain. Мы можем сделать это, остановившись на элементе с максимальным endGain, при условии, что он находится справа от i.
Как показано выше, для каждого i нам нужно найти максимальное значение endGain справа от него.
maxEndRight[i] = max(maxEndRight[i+1], endGain[i+1]) = max(maxEndRight[i+1], a[i+1] – (i+1))
maxEndRight[i] представляет наивысший endGain, который вы можете получить, остановившись в любой точке строго справа от i. Поскольку по определению мы уже знаем endGain[i+1] (наивысший возможный выигрыш при завершении в любой точке справа от i+1), нам нужно только проверить возможность узнать, будет ли выгодна остановка s в точке i+1. или нет. Отсюда и определение ДП.
Для каждого действительного i общее усиление[i] = startGain[i] + maxEndRight[i] = a[i] + i + maxEndRight[i]
Обратите внимание, что maxEndRight[i] зависит только от maxEndRight[i+1]. Следовательно, мы можем использовать 2 переменные для отслеживания предыдущих значений.
Поскольку нам нужно значение maxEndRight[i+1] для вычисления значения maxEndRight[i], мы начинаем итерации с конца.
Как уже говорилось, поездки не могут начинаться с последнего элемента, поэтому цикл for начинается с i=n-2. Для этого значения maxEndingRight инициализируется как endGain[lastIndex], поскольку это единственный возможный способ завершить поездку.
RU 
FR 
EN 
ES