Skip to content

Одномерная DP (1D DP)

1D DP - это метод решения задач, где состояние можно описать одной переменной, а решение строится на основе предыдущих вычислений.

Основные бласти применения

  1. Биотехнологии и медицина (анализ последовательностей ДНК/РНК, поиск паттернов)
  2. Экономика и финансы (прогнозирование временных рядов, выявление трендов)
  3. Обработка текста (поиск повторяющихся фрагментов, исправление ошибок)
  4. Компьютерное зрение (сопоставление одномерных сигналов, например, в спектроскопии)
  5. Логистика (оптимизация маршрутов на основе исторических данных перемещений)

Основные принципы

  1. Определение состояния: Выбираем параметр, который полностью описывает подзадачу (обычно это индекс в массиве).
  2. Рекурентное соотношение: Формулируем, как решение для текущего состояния зависит от предыдущих.
  3. Базовый случай: Определяем тривиальные случаи, с которых начинается заполнение таблицы.
  4. Порядок заполнения: Выбираем направление вычислений (обычно слева направо).
  5. Оптимизация памяти: Часто можно хранить только последние несколько значений вместо всей таблицы.

Пример задачи: Числа Фибоначчи

Классический пример одномерной DP - вычисление чисел Фибоначчи, где каждое число является суммой двух предыдущих.

Решение на Python

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1

    # Инициализируем массив для хранения промежуточных результатов
    dp = [0] * (n + 1)
    dp[0] = 0  # Базовый случай
    dp[1] = 1  # Базовый случай

    # Заполняем массив по порядку
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # Рекуррентное соотношение

    return dp[n]

# Пример использования
print(fibonacci(10))  # Вывод: 55

Оптимизированная версия (с экономией памяти)

def fibonacci_optimized(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1

    prev_prev = 0  # F(n-2)
    prev = 1       # F(n-1)

    for _ in range(2, n + 1):
        current = prev + prev_prev
        prev_prev, prev = prev, current  # Сдвигаем значения

    return prev

print(fibonacci_optimized(10))  # Вывод: 55

Более сложный пример: Задача о кузнечике

Условие: Кузнечик находится в позиции 1 на числовой прямой. Он может прыгать на +1 или +2. Сколькими способами он может добраться до позиции N?

Решение

def count_ways(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2  # 1+1 или 2

    dp = [0] * (n + 1)
    dp[1] = 1  # Базовый случай
    dp[2] = 2  # Базовый случай

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # Способы добраться до i-1 и сделать прыжок +1
                                       # плюс способы добраться до i-2 и сделать прыжок +2

    return dp[n]

print(count_ways(5))  # Вывод: 8 (1111, 112, 121, 211, 22, 1112, 1121, 1211, ...)

Ключевые моменты

  1. Одномерная DP часто применяется для задач последовательностей.
  2. Временная сложность обычно \(O(n)\), пространственная \(O(n)\) или \(O(1)\) при оптимизации.
  3. Важно правильно определить рекуррентное соотношение и базовые случаи.