Алгоритми та структури даних · Middle · Запитання 44 з 75
Яка складність DP для розміну суми A монетами k видів?
- 1O(kᴬ)
- 2O(A + k)
- ✓Правильна відповідь: O(A × k)
Пояснення
Для кожної суми від 1 до A пробуємо кожну з k монет один раз. Експоненційне O(kᴬ) - це рекурсія повного перебору без кешу.
Перевірте себе
Пройдіть тест Алгоритми та структури даних · Middle: запитання й варіанти перемішуються, а наприкінці - розбір помилок.