Динамическое программирование – это мощный метод оптимизации, который применяется для решения задач, обладающих свойствами оптимальной подструктуры и перекрывающимися подзадачами. Задача: Дана последовательность чисел. Найти длину наибольшей возрастающей подпоследовательности. Решение: Псевдокод: for i in range(1, n): for j...

Задача из темы "Рекурсия, перебор", поэтому решим её через рекурсию, но также рассмотрим решение методом динамического программирования. Читаем условие: Рекурсия Разобьём нашу задачу размера N на подзадачи меньшего размера. Однако нельзя вычислить количество лесенок из N кубиков, зная ответы для меньшего числа, потому что они будут включать лесенки с одним кубиком на вершине (а такие лесенки никак не увеличить). Поэтому подзадачи будут с двумя параметрами: сколько существует лесенок из N кубиков, чтобы верхний ряд содержал не меньше M...