Алгоритми та структури даних · Middle · Запитання 42 з 75
Сходи: за крок можна піднятися на 1 або 2 сходинки. Скількома способами можна піднятися на n сходинок?
- 1
ways(n) = 2 ** n, бо кожен крок має два варіанти - 2
ways(n) = n * 2, одна чи дві сходинки на кожну - ✓Правильна відповідь:
ways(n) = ways(n - 1) + ways(n - 2), рекурентність Фібоначчі
Пояснення
Останній хід - або один крок зі сходинки n - 1, або подвійний із n - 2, тож кількості додаються. З двома змінними це O(n) часу й O(1) пам'яті.