Рекурсия, ДП и бинарный поиск

Три навыка, которые отличают «решаю перебором» от «решаю за нужную сложность»: сводить задачу к меньшей, запоминать уже вычисленное и половинно делить пространство поиска.

70.

Climbing Stairs

Easy динамика рекурсия

Лестница состоит из n ступеней. За один шаг можно подняться на 1 или на 2 ступени. Сколькими различными способами можно подняться наверх?

Ограничения: 1 ≤ n ≤ 45.
Пример 1
n = 2
output = 2           # 1+1, 2
Пример 2
n = 3
output = 3           # 1+1+1, 1+2, 2+1
Подсказка

Чтобы стоять на ступени i, вы либо пришли с i−1, либо с i−2. Значит f(i) = f(i−1) + f(i−2) — это почти числа Фибоначчи. Наивная рекурсия без запоминания даёт экспоненциальное время.

Решение 
def climb_stairs(n):
    a, b = 1, 1                 # f(0), f(1)
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Сложность: время O(n), память O(1).

Тот же рекуррентный шаг — в задачах Codewars N-th Fibonacci и Simple Memoization: там мемоизация нужна явно, иначе наивная рекурсия не укладывается в время.

78.

Subsets

Medium рекурсия / бэктрекинг битовые маски

Дан массив различных целых чисел nums. Верните все возможные подмножества (степень множества). Ответ не должен содержать дубликатов, порядок не важен.

Ограничения: 1 ≤ nums.length ≤ 10 — вывод заведомо экспоненциальный: 2ⁿ подмножеств.
Пример 1
nums = [1, 2, 3]
output = [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
Пример 2
nums = [0]
output = [[], [0]]
Подсказка

Два стандартных взгляда. Рекурсия: для каждого элемента есть два выбора — берём или не берём (дерево глубины n). Битовая маска: перебрать числа от 0 до 2ⁿ−1, где установленные биты говорят, какие элементы входят.

Решение 
def subsets(nums):                    # бэктрекинг
    answer, path = [], []

    def backtrack(start):
        answer.append(path[:])        # копия текущего набора
        for i in range(start, len(nums)):
            path.append(nums[i])      # берём
            backtrack(i + 1)          # идём только вперёд — нет дублей
            path.pop()                # откат

    backtrack(0)
    return answer
def subsets_bitmask(nums):            # битовые маски
    n = len(nums)
    return [[nums[b] for b in range(n) if mask >> b & 1]
            for mask in range(1 << n)]

Сложность: время O(n · 2ⁿ), память O(n) сверх выходных данных.

339.

Nested List Weight Sum

Medium рекурсия DFS

Дан вложенный список, элементами которого могут быть целые числа или такие же списки. Найдите сумму всех целых чисел, умноженных на их глубину вложенности. Числа на верхнем уровне имеют глубину 1, каждый вложенный список увеличивает глубину на 1.

Ограничения: структура конечна, циклов нет, всего чисел не более 500.
Пример 1
lst = [1, 1, 2, [1, 1]]    # 1·1 + 1·1 + 2·1 + 1·2 + 1·2
output = 8
Пример 2
lst = [1, [4, [6]]]        # 1·1 + 4·2 + 6·3
output = 27

lst = []                   # пустой список
output = 0
Подсказка

Идите вглубь с параметром «текущая глубина»: встретили число — прибавьте число · глубина, встретили список — рекурсивно обойдите его с глубина + 1.

Решение 
# class NestedInteger:
#     def isInteger(self) -> bool: ...
#     def getInteger(self) -> int | None: ...
#     def getList(self) -> list["NestedInteger"]: ...

def depth_sum(nested_list, depth=1):
    total = 0
    for item in nested_list:
        if item.isInteger():
            total += item.getInteger() * depth
        else:
            total += depth_sum(item.getList(), depth + 1)
    return total
def depth_sum_iterative(nested_list):   # без рекурсии, явным стеком
    stack, total = [(item, 1) for item in reversed(nested_list)], 0
    while stack:
        item, depth = stack.pop()
        if item.isInteger():
            total += item.getInteger() * depth
        else:
            for child in reversed(item.getList()):
                stack.append((child, depth + 1))
    return total

Сложность: время O(N) — по числу всех элементов, память O(D), где D — максимальная глубина (стек вызовов или свой стек).