составить тесты с ответами по математическому динамическому программированию

Ниже приведен набор тестовых задач по математическому динамическому программированию с подробными решениями и ответами. Уровень — средней школы: понятная постановка, прямые рекуррентные соотношения и пошаговые вычисления.

Задача 1

• Условие: Сколько способов добраться до ступени n, если можно сделать шаг 1 или 2? Введите общее решение и посчитайте для n = 7.
• Решение:
  • Пусть f(n) — число способов дойти до ступени n.
  • Базовые случаи: f(0) = 1 (один способ остаться на месте), f(1) = 1 (только один шаг на 1).
  • Рекуррентное соотношение: f(n) = f(n-1) + f(n-2) для n ≥ 2.
  • Вычисление: f(2)=f(1)+f(0)=1+1=2; f(3)=f(2)+f(1)=2+1=3; f(4)=5; f(5)=8; f(6)=13; f(7)=21.
• Ответ: 21 способ.

Задача 2

• Условие: В наборе предметов есть три предмета с весами и стоимостями: (w,v) = (1,6), (3,10), (4,12). Вместимость рюкзакаW = 5. Каждый предмет можно взять не более одного раза. Найдите максимальную стоимость.
• Решение:
  • Это задача 0/1 рюкзака. Обозначим dp[i][w] максимальную стоимость, используя первых i предметов и вместимость w.
  • Базовые случаи: dp[0][w] = 0; dp[i][0] = 0.
  • Перебираем предметы:
    • Для предмета 1 (w=1, v=6): для w=1..5 обновляем dp.
    • Для предмета 2 (w=3, v=10)
    • Для предмета 3 (w=4, v=12)
  • Альтернатива: простой перебор вручную по максимуму:
    • Вариант взять предметы 1 и 3: вес 1+4 = 5, стоимость 6+12 = 18.
    • Вариант взять 2 и 3: вес 3+4 = 7 > 5 (нельзя).
    • Вариант взять 1 и 2: вес 1+3 = 4, стоимость 6+10 = 16.
    • Вариант взять только 3: вес 4, стоимость 12.
    • Вариант взять только 2: вес 3, стоимость 10.
  • Лучший вариант: предметы 1 и 3, стоимость 18.
• Ответ: 18.

Задача 3

• Условие: Найдите длину наибольшей возростающей подпоследовательности (LIS) в массиве A = [10, 9, 2, 5, 3, 7, 101, 18].
• Решение:
  • Пусть dp[i] — длина LIS, заканчивающейся на элементе i.
  • Базовый случай: dp[i] ≥ 1.
  • Рекуррентное: dp[i] = 1 + max(dp[j]) по всем j < i, где A[j] < A[i].
  • Вычисление по шагам (упрощенно):
    • LIS заканчивающиеся на 10: 1
    • на 9: 1
    • на 2: 1
    • на 5: максимум до 5 с меньшими: можно продолжить от 2 → 2, значит dp(5)=2
    • на 3: от 2 → 2
    • на 7: можно продолжить от 2 или 3: dp(7)=3
    • на 101: можно продолжить от 7: dp(101)=4
    • на 18: можно продолжить от 7 или 3: dp(18)=4
  • Максимум dp = 4.
• Ответ: 4.

Задача 4

• Условие: Найдите длину наибольшей общей подпоследовательности (LCS) между строками X = "AGGTAB" и Y = "GXTXAYB".
• Решение:
  • Пусть dp[i][j] — длина LCS между префиксами X[0..i-1] и Y[0..j-1].
  • Базовые случаи: dp[0][j] = dp[i][0] = 0.
  • Рекуррентное:
    • если X[i-1] == Y[j-1], то dp[i][j] = dp[i-1][j-1] + 1
    • иначе dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  • Применение к данными строкам: LCS длиной 4 (например, "GTAB").
• Ответ: 4.

Задача 5

• Условие: Сколько двоичных строк длины n без двух соседних единиц? Найдите для n = 5.
• Решение:
  • Пусть f(n) — число таких строк.
  • Базовые: f(0) = 1 (пустая строка), f(1) = 2 (0,1).
  • Рекуррентное: f(n) = f(n-1) + f(n-2) (если в начале ставим 0, или 10… начинаем с 1 и следующая позиция начинается с 0).
  • Вычисление: f(2) = 3, f(3) = 5, f(4) = 8, f(5) = 13.
• Ответ: 13.

Задача 6

• Условие: Сколько способов застелить длинную прямоугольную дорожку ширины 2 клетки и длины n клеток domino-ками размером 2×1? Найдите для n = 5.
• Решение:
  • Это стандартная задача для покрытия 2×n domino-ками.
  • Обозначим T(n) число способов. Рекуррентное: T(n) = T(n-1) + T(n-2) с базами T(1) = 1, T(2) = 2.
  • Вычисление: T(3) = 3, T(4) = 5, T(5) = 8.
• Ответ: 8.

Задача 7

• Условие: Сколько способов добраться до n-го шага, если можно сделать шаг 1, 2 или 3? Найдите для n = 5.
• Решение:
  • Пусть g(n) — число способов.
  • Базовые: g(0) = 1, g(1) = 1, g(2) = 2.
  • Рекуррентное: g(n) = g(n-1) + g(n-2) + g(n-3) для n ≥ 3.
  • Вычисление: g(3) = 4, g(4) = 7, g(5) = 13.
• Ответ: 13.

Задача 8

• Условие: Дано поле 3×3 с неотрицательными затратами на клетки: 1 3 2 4 6 5 2 1 1 Пусть можно перемещаться только вправо или вниз. Найдите минимальную возможную сумму затрат на путь от верхнего левого к нижнему правому углу (включая стоимость начальной и конечной клеток).
• Решение:
  • Пусть dp[i][j] — минимальная сумма до клетки (i, j).
  • Базовые: dp[0][0] = 1.
  • Первые строки и столбцы: накапливаем слева и сверху.
  • Остальные: dp[i][j] = стоимость[i][j] + min(dp[i-1][j], dp[i][j-1]).
  • Применение к данному полю: dp:
    • первая строка: [1, 4, 6]
    • первый столбец: [5, 9, 11]
    • dp[1][1] = 6 + min(4,5) = 6+4 = 10 dp[1][2] = 5 + min(6,10) = 5+6 = 11 dp[2][1] = 1 + min(10,9) = 1+9 = 10 dp[2][2] = 1 + min(11,10) = 1+10 = 11
  • Итоговая минимальная сумма в dp[2][2] = 9? Перепроверим расчеты корректно: Правильная последовательность: Начало: dp[0][0] = 1 dp[0][1] = dp[0][0] + 3 = 4 dp[0][2] = dp[0][1] + 2 = 6 dp[1][0] = dp[0][0] + 4 = 5 dp[2][0] = dp[1][0] + 2 = 7 dp[1][1] = cost(1,1)=6 + min(dp[0][1], dp[1][0]) = 6 + min(4,5) = 10 dp[1][2] = 5 + min(dp[0][2], dp[1][1]) = 5 + min(6,10) = 11 dp[2][1] = 1 + min(dp[1][1], dp[2][0]) = 1 + min(10,7) = 8 dp[2][2] = 1 + min(dp[1][2], dp[2][1]) = 1 + min(11,8) = 9
  • Ответ = 9.
• Ответ: 9.

Задача 9

• Условие: Пусть Cn — число различных бинарных поисковых деревьев (BST) с n узлами. Найдите C3.
• Решение:
  • ЧислоBST с n узлами равно каталановым числам: Cn = sum_{i=1..n} Ci-1 * Cn-i, с C0 = 1.
  • Применяя для n = 1,2,3:
    • C0 = 1
    • C1 = C0*C0 = 1
    • C2 = C0C1 + C1C0 = 1 + 1 = 2
    • C3 = C0C2 + C1C1 + C2*C0 = 2 + 1 + 2 = 5
• Ответ: 5.

Задача 10

• Условие: Сколько способов составить число 7 монетами из множества номиналов {1, 3, 4}, если монеты можно использовать любое количество раз? Порядок не имеет значения.
• Решение:
  • Это задача счетчика сочетаний с повторениями. Используем DP по монетам:
    • Пусть ways[i] — число способов составить сумму i.
    • Инициализация: ways[0] = 1, остальные 0.
    • Сначала обрабатываем монету 1: для i = 1..7 ways[i] += ways[i-1] → после этого ways[i] = 1.
    • Затем монета 3: для i = 3..7 ways[i] += ways[i-3].
      • i=3: ways[3] = 1 + ways[0] = 2
      • i=4: ways[4] = 1 + ways[1] = 2
      • i=5: ways[5] = 1 + ways[2] = 2
      • i=6: ways[6] = 1 + ways[3] = 1 + 2 = 3
      • i=7: ways[7] = 1 + ways[4] = 1 + 2 = 3
    • Затем монета 4: для i = 4..7 ways[i] += ways[i-4].
      • i=4: ways[4] = 2 + ways[0] = 3
      • i=5: ways[5] = 2 + ways[1] = 3
      • i=6: ways[6] = 3 + ways[2] = 4
      • i=7: ways[7] = 3 + ways[3] = 3 + 2 = 5
  • Итог: ways[7] = 5.
• Ответ: 5.

Краткое резюме

• Для всех задач применялись общие принципы DP: вводим подходящую DP-переменную (массив или набор значений), задаем базовые случаи, формируем рекуррентное соотношение и выполняем вычисления по шагам. Это типичный набор задач по математическому динамическому программированию, охватывающий как задачи счёта путей и разрезов, так и задачи оптимизации и комбинаторики.

Если хотите, могу дополнить тесты другими темами DP (например, выпуклая оптимизация, DP на деревьях, динамическое программирование на графах) или сделать тесты в формате «мультпунктовый выбор» с ответами.