Разбор задачи «График полезных дней»

Идея задачи

У нас есть n дней. Для каждого дня известно, что можно делать:

• 0 — только отдыхать;
• 1 — отдыхать или решать задачи;
• 2 — отдыхать или тренироваться;
• 3 — отдыхать, решать задачи или тренироваться.

Нужно составить план так, чтобы количество дней отдыха было минимальным.

При этом есть важное ограничение:

• нельзя решать задачи два дня подряд;
• нельзя тренироваться два дня подряд.

Отдыхать подряд можно сколько угодно.

Главная трудность задачи в том, что хорошее решение на текущий день зависит от того, что мы делали в предыдущий день. Именно это подсказывает идею динамического программирования.

Почему жадный подход здесь неудобен

Можно подумать так:

• если сегодня можно не отдыхать, то не будем отдыхать;
• если доступны обе активности, выберем любую.

Но такой подход может привести к неудачному выбору. Иногда выгоднее сегодня выбрать одну активность, чтобы завтра тоже избежать отдыха.

Значит, нужно не просто принимать локальное решение, а хранить информацию о том, каким действием закончился предыдущий день.

Состояния динамики

Будем хранить:

dp[i][state] — минимальное количество дней отдыха после первых i дней, если в i-й день мы закончили действием state.

Обозначим состояния так:

• 0 — в i-й день отдыхали;
• 1 — в i-й день решали задачи;
• 2 — в i-й день тренировались.

Тогда ответом будет:

min(dp[n][0], dp[n][1], dp[n][2])

потому что нас интересует лучший вариант после всех n дней.

База динамики

До начала дней у нас нет ни отдыха, ни задач, ни тренировок.

Удобно положить:

• dp[0][0] = 0
• dp[0][1] = 0
• dp[0][2] = 0

Это техническая инициализация, которая упрощает переходы.

Переходы

1. Отдых

Отдыхать можно всегда, независимо от того, что было вчера.

Значит:

dp[i][0] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + 1

Почему +1? Потому что текущий день становится днем отдыха.

2. Решение задач

Если в день i разрешено решать задачи (a[i] = 1 или a[i] = 3), то перейти в состояние 1 можно только из тех состояний, где вчера мы не решали задачи.

То есть:

dp[i][1] = min(dp[i-1][0], dp[i-1][2])

Переход из dp[i-1][1] запрещен, потому что нельзя решать задачи два дня подряд.

3. Тренировка

Если в день i разрешена тренировка (a[i] = 2 или a[i] = 3), то перейти в состояние 2 можно только из состояний, где вчера не было тренировки.

То есть:

dp[i][2] = min(dp[i-1][0], dp[i-1][1])

Переход из dp[i-1][2] запрещен.

Почему этого достаточно

Для принятия решения на день i нам важно только:

• сколько дней отдыха уже набралось;
• что было в день i-1.

Более далекая история уже не влияет на допустимость текущего выбора.

Именно поэтому достаточно хранить только последнее действие.

Пошаговый пример

Пусть:

n = 4
a = [1, 3, 2, 0]

Разберем по дням.

День 1, a[1] = 1

Можно отдыхать или решать задачи.

• отдых: 1
• задачи: 0
• тренировка: невозможно

Получаем:

• dp[1][0] = 1
• dp[1][1] = 0
• dp[1][2] = INF

День 2, a[2] = 3

Можно все.

• отдых: min(1, 0, INF) + 1 = 1
• задачи: min(1, INF) = 1
• тренировка: min(1, 0) = 0

Получаем:

• dp[2][0] = 1
• dp[2][1] = 1
• dp[2][2] = 0

День 3, a[3] = 2

Можно отдыхать или тренироваться.

• отдых: min(1, 1, 0) + 1 = 1
• тренировка: min(1, 1) = 1

Получаем:

• dp[3][0] = 1
• dp[3][1] = INF
• dp[3][2] = 1

День 4, a[4] = 0

Можно только отдыхать.

• отдых: min(1, INF, 1) + 1 = 2

Итоговый ответ: 2.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    const int INF = 1e9;
    vector<vector<int>> dp(n + 1, vector<int>(3, INF));

    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[0][2] = 0;

    for (int i = 1; i <= n; i++) {
        dp[i][0] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]}) + 1;

        if (a[i] == 1 || a[i] == 3) {
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]);
        }

        if (a[i] == 2 || a[i] == 3) {
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]);
        }
    }

    cout << min({dp[n][0], dp[n][1], dp[n][2]}) << '\n';
    return 0;
}

Реализация на Python

n = int(input())
a = list(map(int, input().split()))

INF = 10 ** 9
dp = [[INF] * 3 for _ in range(n + 1)]

dp[0][0] = 0
dp[0][1] = 0
dp[0][2] = 0

for i in range(1, n + 1):
    dp[i][0] = min(dp[i - 1]) + 1

    if a[i - 1] == 1 or a[i - 1] == 3:
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2])

    if a[i - 1] == 2 or a[i - 1] == 3:
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1])

print(min(dp[n]))

Оптимизация по памяти

Так как dp[i] зависит только от dp[i-1], можно хранить не всю таблицу, а только три значения для предыдущего дня.

Это уменьшит память до O(1).

Но для обучения и для методического разбора вариант с таблицей обычно лучше:

• он нагляднее;
• проще объясняется;
• легче проверяется новичками.

Асимптотика

На каждом из n дней мы делаем константное количество операций.

Поэтому:

• время: O(n)
• память: O(n)

Типичные ошибки

1. Забывают, что отдых разрешен всегда

Даже если день допускает задачи или тренировку, отдых все равно можно выбрать.

2. Разрешают одинаковую активность два дня подряд

Нельзя переходить:

• из задач в задачи;
• из тренировки в тренировку.

Это главное ограничение задачи.

3. Неправильно понимают значение числа 3

3 означает, что доступны обе активности: и задачи, и тренировка.

4. Путают индексацию в Python

В C++ массив удобно делать с индексацией с 1, а в Python входной массив обычно идет с 0.

Из-за этого легко ошибиться в обращении к a[i] и a[i - 1].

Вывод

Это классическая задача на динамическое программирование по дням и последнему действию.

Ключевая идея очень важна:

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

Здесь достаточно помнить только одно: чем закончился прошлый день.

После этого задача решается коротко, аккуратно и за линейное время.