DEV//UNIT
01 / Раздел

АЛГОРИТМЫ

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

Dynamic Programming

TSP: битовое DP (Held-Karp)

Коммивояжёр за 2ⁿ·n²: подмножества городов в битах маски.

массивпродвинутыйO(2ⁿ · n²)

Алгоритм Кадане

Максимальная сумма подотрезка за один проход: текущая сумма либо растёт, либо сбрасывается.

массивначальныйO(n)

Дом-грабитель

Грабить дома нельзя два подряд: взять или пропустить — два бегущих максимума.

столбикиначальныйO(n)

Лестница (шаг 1 или 2)

Сколькими способами подняться по лестнице — это Фибоначчи в костюме задачи.

массивначальныйO(n)

Минимальный путь по сетке

Из угла в угол по сетке, только вправо и вниз — минимальная сумма маршрута.

массивначальныйO(rows·cols)

Наибольшая возрастающая подпоследовательность

Самая длинная цепочка роста — элементы можно пропускать.

столбикисреднийO(n²)

Порядок умножения матриц

Где ставить скобки: порядок умножений меняет стоимость в разы.

массивсреднийO(n³)

Рюкзак 0/1

Что взять в рюкзак при лимите веса: каждая вещь либо в рюкзаке, либо нет.

массивсреднийO(n · capacity)

Сдача минимальным числом монет

Набрать сумму минимальным числом монет — жадность часто врёт, динамика честна.

массивсреднийO(amount · монеты)