Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 14.8 Упражнения

## 14.8.1 Вопросы для самопроверки

### 1. Когда подходит динамическое программирование

Ученик утверждает: «Если можно записать рекуррентное соотношение, нужно использовать динамическое программирование». Для каждой из трех задач выберите наиболее подходящий из трех вариантов: динамическое программирование; поиск с возвратом; цикл или математическая формула без таблицы `dp`. Укажите одну основную причину.

1. Набрать сумму 6 с помощью монет номиналов `[1, 3, 4]`, используя каждый номинал любое число раз, и найти минимальное число монет;
2. вывести все перестановки `[1, 2, 3]`;

3. вычислить \(1 + 2 + \dots + n\).

   Для задачи, которой подходит динамическое программирование, также объясните значение `dp[i]`.

Ответ

1. Подходит динамическое программирование. Пусть `dp[i]` — минимальное число монет, необходимое для получения суммы `i`. Для каждой монеты `c`, не превосходящей `i`, значение `dp[i-c] + 1` можно рассматривать как возможный ответ, а затем выбрать минимум среди всех вариантов. Разные последовательности выбора многократно приводят к одной и той же сумме, а оптимальное решение для большей суммы можно составить из оптимальных решений для меньших сумм. Для суммы 6 ответ равен 2: `3 + 3`.

2. Следует использовать поиск с возвратом. Задача требует поочередно получить все 6 перестановок; поиск с возвратом позволяет систематически сделать выбор, продолжить поиск, затем отменить выбор и перейти к другой ветви. Каким бы ни был метод, при фактическом выводе всех перестановок пропустить их перебор нельзя.

3. Достаточно цикла или формулы суммы арифметической прогрессии. Хотя можно записать `S(i) = S(i-1) + i`, при вычислении `S(i)` требуется только одно меньшее значение `S(i-1)`, а каждая частичная сумма вычисляется один раз. Повторяющихся подзадач нет, поэтому таблица `dp` не нужна. Возможность записать рекуррентное соотношение не означает необходимости динамического программирования.

### 2. Как вычислить одну ячейку таблицы рюкзака

Задача о рюкзаке 0-1: веса предметов `wgt = [1, 2, 3]`, их стоимости `val = [5, 11, 15]`, вместимость рюкзака равна 4. `dp[i][c]` — максимальная стоимость, которую можно получить, рассматривая только первые \(i\) предметов при предельной вместимости рюкзака \(c\); заполнять рюкзак точно до предела не требуется.

Вычислите только состояние `dp[3][4]`. Известно, что `dp[2][4] = 16` и `dp[2][1] = 5`.

1. Какова возможная стоимость, если не брать 3-й предмет?
2. Какая вместимость останется, если взять 3-й предмет, и чему равна возможная стоимость?
3. Какое значение нужно присвоить `dp[3][4]`? Какие предметы ему соответствуют?

Ответ

1. Если не брать 3-й предмет, сохраняется результат для первых двух предметов, поэтому возможная стоимость равна `dp[2][4] = 16`.

2. Вес 3-го предмета равен 3, после его добавления остается вместимость \(4-3=1\). Возможная стоимость равна `dp[2][1] + 15 = 5 + 15 = 20`.

3. Сравнив 16 и 20, получаем `dp[3][4] = 20`. Это соответствует выбору 1-го и 3-го предметов: их общий вес равен \(1+3=4\), а общая стоимость — \(5+15=20\).

   Вычисление этого состояния показывает один выбор в задаче о рюкзаке 0-1: «взять или не взять».

### 3. В каком порядке обновлять вместимость рюкзака

В задаче о рюкзаке 0-1 есть только один предмет весом 2 и стоимостью 5; вместимость рюкзака равна 4. Каждый предмет разрешено выбрать не более одного раза, а исходный одномерный массив имеет вид `dp = [0, 0, 0, 0, 0]`.

Обрабатывая предмет, ученик обновляет вместимость от 2 до 4:

- после обновления `dp[2]` получается 5;
- после обновления `dp[3]` также получается 5;
- при обновлении `dp[4]` снова используется только что полученное `dp[2]`, поэтому выходит `dp[4] = 10`.

1. Правилен ли результат `dp[4] = 10`? Почему?
2. Чему должно быть равно `dp[4]`, если каждый предмет можно выбрать не более одного раза?
3. При обработке каждого предмета вместимость нужно перебирать от большей к меньшей или от меньшей к большей? Какую проблему предотвращает такой порядок?

Ответ

1. Результат неверен. Стоимость 10 означает, что предмет стоимостью 5 положили в рюкзак дважды, нарушив условие «каждый предмет можно выбрать не более одного раза».

2. В рюкзак можно положить не более одного такого предмета, поэтому правильное значение `dp[4]` равно 5.

3. Вместимость нужно обновлять от большей к меньшей, то есть в порядке 4, 3, 2. Тогда при вычислении `dp[c]` читаемое значение `dp[c-2]` все еще относится к состоянию до обработки текущего предмета, и этот предмет нельзя повторно использовать на той же итерации.

## 14.8.2 Задачи по программированию

### 1. Число способов подняться по лестнице

Лестница состоит из `n` ступеней. За один шаг можно подняться только на 1 или 2 ступени, причем нужно попасть точно на ступень `n`. Вычислите число различных способов подъема. Считайте, что `n >= 1`; способы различаются только последовательностью шагов на 1 и 2 ступени. Используйте одномерный массив динамического программирования; пока не применяйте оптимизацию памяти, сохраняющую лишь два состояния.

Подсказки

1. Последний шаг на ступень i мог быть только на 1 или на 2 ступени
2. Поэтому dp[i] = dp[i-1] + dp[i-2]
3. Сначала обработайте случаи n, равного 1 и 2, а затем заполняйте таблицу начиная с 3-й ступени

LeetCode

### 2. Рюкзак 0-1

Даны массивы одинаковой длины `wgt` и `val`: вес предмета `i` — положительное целое число `wgt[i]`, а его стоимость — неотрицательное целое число `val[i]`. Вместимость рюкзака `cap` — неотрицательное целое число. Каждый предмет можно выбрать не более одного раза. Найдите максимальную суммарную стоимость предметов, общий вес которых не превышает `cap`. Используйте одномерное динамическое программирование.

Подсказки

1. Создайте массив dp длины cap + 1, где dp[c] — максимальная стоимость при предельной вместимости c
2. Обрабатывая предмет i, сравните dp[c] для варианта «не брать предмет» и dp[c-wgt[i]] + val[i] для варианта «взять предмет»
3. Вместимость нужно обновлять от большей к меньшей, чтобы не выбрать текущий предмет повторно на одной итерации

##### Оставляйте свои идеи, вопросы и предложения в комментариях