⚙️ Алгоритмы · 20 вопросов · ~45 мин · ⏱ Таймер 45:00 · Сложный ·

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

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

Отвечено: 0 из 20

⏱ --:--

💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 45 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.

Вопрос 1 из 20

Что означает dp[i] в этой программе?

dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
    if i >= 1:
        dp[i] += dp[i - 1]
    if i >= 2:
        dp[i] += dp[i - 2]

Минимальное число шагов до i Число способов набрать i шагами длины 1 и 2 Последний сделанный шаг Максимальная сумма на префиксе i

Вопрос 2 из 20

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

cost = [
    [4, 1, 7],
    [2, 5, 1],
    [3, 2, 6],
]
rows, cols = len(cost), len(cost[0])
dp = [[float('inf')] * cols for _ in range(rows)]
# Нужно определить смысл dp[i][j] для пути из (0, 0)
# с ходами только вправо и вниз.

dp[i][j] — минимальная стоимость пути до клетки (i,j) Множество всех когда-либо посещённых клеток Одна переменная с координатой последнего хода без стоимости dp[i] — число клеток в строке i

Вопрос 3 из 20

Для 0/1-рюкзака стандартное состояние dp[i][w] обычно означает:

Максимальную ценность из первых i предметов при вместимости w Минимальную вместимость для любого числа предметов без ограничения i Вес i-го предмета после сортировки Число всех перестановок предметов

Вопрос 4 из 20

Почему одной координаты позиции недостаточно в задаче пути с ограничением «можно разрушить не более одной стены»?

from collections import deque

start = (0, 0, 0)  # строка, столбец, число разрушенных стен
queue = deque([start])
visited = {start}
while queue:
    row, col, broken = queue.popleft()
    for nr, nc in neighbours(row, col):
        next_broken = broken + (grid[nr][nc] == '#')
        if next_broken <= 1:
            state = (nr, nc, next_broken)
            if state not in visited:
                visited.add(state)
                queue.append(state)

Достаточно хранить минимальное число шагов до клетки независимо от использованного разрушения Нужно добавить в состояние признак, использовано ли разрушение Нужно добавить направление последнего шага, а использование стены не влияет на будущее Можно оставить только координаты, если обход идёт слоями BFS

Вопрос 5 из 20

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

dp_i=1+\max_{j<i,\ a_j<a_i}dp_j

dp[i] — длина лучшей возрастающей подпоследовательности с последним элементом a[i] dp[i] — наибольшая сумма элементов префикса a[0..i] независимо от их порядка dp[i] — число элементов правее i, значения которых превосходят a[i] dp[i] — позиция минимального элемента массива, найденная к моменту обработки i

Вопрос 6 из 20

Какое значение dp[5] будет вычислено?

dp[x]=\min_{c\le x}\bigl(dp[x-c]+1\bigr)

coins = [1, 3, 4]
INF = 10**9
dp = [0] + [INF] * 6
for amount in range(1, 7):
    for coin in coins:
        if coin <= amount:
            dp[amount] = min(dp[amount], dp[amount - coin] + 1)
print(dp[5])

5 1 2 3

Вопрос 7 из 20

Какой переход считает число путей по сетке без препятствий?

rows, cols = 4, 5
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = 1
for i in range(rows):
    for j in range(cols):
        if i == 0 and j == 0:
            continue
        # Здесь нужно выразить dp[i][j]
        # через уже вычисленные соседние клетки.

dp[i][j] = i + j dp[i][j] = dp[i-1][j-1] dp[i][j] = max(dp[i-1][j], dp[i][j-1]) dp[i][j] = dp[i-1][j] + dp[i][j-1]

Вопрос 8 из 20

В 0/1-рюкзаке при одномерной таблице почему вместимость w перебирают по убыванию?

Чтобы разрешить брать дробную часть текущего предмета, не создавая нового состояния Чтобы каждый следующий предмет сравнивался только с предметами меньшего веса Чтобы значения dp[w] после обработки предмета располагались по возрастанию вместимости Чтобы один предмет не использовался несколько раз в той же итерации

Вопрос 9 из 20

Какое значение получится для dp[3]?

a = [3, 1, 2, 5]
dp = [1] * len(a)
for i in range(len(a)):
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)
print(dp[3])

5 2 4 3

Вопрос 10 из 20

Как формулируется переход редакционного расстояния при разных последних символах?

Взять минимум удаления, вставки и замены с соответствующей добавленной стоимостью Взять минимум удаления и вставки; замену можно считать их последовательностью с той же ценой Использовать только dp[i−1][j−1]+1, поскольку последние символы различаются Сложить dp[i−1][j] и dp[i][j−1], чтобы учесть оба направления изменения

Вопрос 11 из 20

Сколько способов добраться до ступени 4 посчитает таблица?

n = 4
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
    dp[i] = dp[i - 1]
    if i >= 2:
        dp[i] += dp[i - 2]
print(dp[n])

16 3 8 5

Вопрос 12 из 20

Почему инициализация нулями неверна для минимума монет?

dp = [0] * (amount + 1)
for x in range(1, amount + 1):
    for coin in coins:
        if coin <= x:
            dp[x] = min(dp[x], dp[x - coin] + 1)

Нельзя использовать min в динамическом программировании Монеты нужно сортировать по убыванию Таблица должна иметь отрицательную длину Ноль ошибочно выглядит уже лучшим достижимым ответом для положительных сумм

Вопрос 13 из 20

Как задать базу для числа способов получить сумму 0 без выбора элементов?

0 способов Бесконечно много способов 1 способ — выбрать пустой набор Зависит от номиналов

Вопрос 14 из 20

В каком порядке нужно заполнять таблицу?

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + cost[i][j]

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

Вопрос 15 из 20

Что обычно означает значение ∞ в таблице минимизации?

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

Вопрос 16 из 20

Какой последний номинал будет выбран для суммы 6?

coins = [1, 3, 4]
dp = [0, 1, 2, 1, 1, 2, 2]
parent = [-1] * 7
for x in range(1, 7):
    for coin in coins:
        if coin <= x and dp[x] == dp[x - coin] + 1:
            parent[x] = coin
            break
print(parent[6])

4 1 -1 3

Вопрос 17 из 20

Как восстановить путь из клетки (i,j)?

parent[i][j] = (pi, pj)
# parent хранит предшественника выбранного оптимального перехода

Суммировать координаты Сортировать все клетки по стоимости Идти по parent от финиша к старту и затем развернуть список Начать со старта и угадывать следующую клетку

Вопрос 18 из 20

Почему одной таблицы оптимальных стоимостей иногда недостаточно для восстановления выбранных предметов?

Потому что таблица не хранит размеры предметов, хотя они по-прежнему доступны во входных данных Одинаковая стоимость может быть получена разными переходами, а происхождение не сохранено Потому что для восстановления в любом случае нужен полный перебор подмножеств, независимо от dp Потому что восстановление требует заново считать стоимости в другом порядке, даже если переходы известны

Вопрос 19 из 20

Какие индексы образуют восстановленную LIS?

a = [3, 1, 2, 5, 4]
parent = [-1, -1, 1, 2, 2]
end = 4
path = []
while end != -1:
    path.append(end)
    end = parent[end]
path.reverse()
print(path)

[4,2,1] [0,2,4] [1,2,4] [1,3,4]

Вопрос 20 из 20

Как сжатие памяти с dp[i][j] до одной строки влияет на восстановление пути?

M:O(nm)\to O(m)

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

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу