Вот тест по информатике на тему одномерного динамического программирования на подсчет количества вариантов для 11 класса.

Тест по информатике: Одномерное динамическое программирование на подсчет количества вариантов

Вопрос 1: Какой из следующих вариантов задачи можно решить с помощью одномерного динамического программирования?
A) Нахождение факториала числа
B) Подсчет количества способов разложить заданное число на суммы
C) Поиск наибольшего общего делителя
D) Сортировка массива

Правильный ответ: B) Подсчет количества способов разложить заданное число на суммы

---

Вопрос 2: Какой алгоритм можно использовать для решения задачи о количестве способов разложить число ( n ) на суммы?
A) Жадный алгоритм
B) Динамическое программирование
C) Разделяй и властвуй
D) Обратный поиск

Правильный ответ: B) Динамическое программирование

---

Вопрос 3: В какой ситуации вы можете использовать одномерный массив для хранения результатов промежуточных вычислений?
A) Когда размеры подзадач не зависят от предыдущих результатов
B) Когда результаты подзадач могут переиспользоваться
C) Когда необходимо выполнять поиск в неупорядоченных данных
D) Во всех случаях

Правильный ответ: B) Когда результаты подзадач могут переиспользоваться

---

Вопрос 4: Если вам необходимо посчитать количество способов получить сумму ( n ) с использованием монет ( {1, 2, 3} ), какова будет базовая позиция в вашем динамическом программировании?
A) dp[0] = 1
B) dp[0] = 0
C) dp[n] = 1
D) dp[n] = 0

Правильный ответ: A) dp[0] = 1

---

Вопрос 5: Как вы будете обновлять значения в массиве dp для подсчета количества способов образования суммы ( n ) из заданных чисел?
A) Почему бы не использовать рекурсию?
B) dp[i] += dp[i - coins[j]] для каждого coin
C) dp[i] = dp[i - coins[j]] * 2
D) dp[i] = dp[i] - dp[i - coins[j]]

Правильный ответ: B) dp[i] += dp[i - coins[j]] для каждого coin

---

Вопрос 6: Если у вас есть массив coin = {1, 2} и вы хотите найти количество способов получить сумму 5, сколько способов вы найдете с помощью динамического программирования?
A) 5
B) 8
C) 3
D) 10

Правильный ответ: B) 8

---

Удачи на экзаменах!