Динамическое программирование: теория

• Динамика

Словосочетание динамическое программирование впервые было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 г. он уточнил это определение до современного. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме. Слово «программирование» в словосочетании «динамическое программирование» в действительности к традиционному программированию (написанию кода) почти никакого отношения не имеет и происходит от словосочетания «математическое программирование», которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.

Идея метода динамического программирования состоит в сведении (с помощью рекуррентных соотношений) исходной задачи к решению некоторых ее подзадач «меньшего размера» и использовании табличной техники для сохранения уже найденных ответов [2]. Рассказ о методе динамического программирования уместно начинать с легенды о лестнице фараона [12]. Золотую лестницу фараона из девяти ступеней необходимо было модернизировать, уменьшив количество ступеней в лестнице до четырех и используя небольшое количество золота, имеющееся в казне для наращивания ступеней. Золота было так мало, а всех вариантов модернизации так много, что не сносить бы несчастному казначею головы, если бы не его умный друг-жрец.  Жрец, прекрасно владея чудесным методом динамического программирования, сумел за короткий срок, не рассматривая всех вариантов, найти оптимальное решение и выгадать себе остаток золота из казны фараона.
Разбор задач по данному методу легче воспринимается с самой известной и простой задачи про маршрут [13].

Задача 1. Маршрут по таблице

В таблице $A$ размерности $N \times N$ клетки заполнены случайным образом цифрами от 0 до 9. Найти маршрут из левой верхней клетки $A(1, 1)$ в правую нижнюю клетку $A(N, N)$ такой, что:

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

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

Очевидно, что все кратчайшие маршруты идут только сверху вниз и слева направо и число клеток в каждом из них $2N-1$. При достаточно большом $N$ таких маршрутов огромное количество, что полным перебором решить данную задачу практически невозможно.

Итак, рассмотрим аналогичную задачу для всевозможных прямоугольных подтаблиц размеров $(N-I+1) \times (N-J+1)$ исходной таблицы (при $I, J = 1, 2, ...$) и построим вспомогательную таблицу $B$ размером $N \times N$ с суммой цифр, через которые проходит оптимальный путь в такой таблице.
Построение вспомогательной таблицы $B$ необходимо начать с конца таблицы $A$, что приведет к следующим формулам (рис. 1):

1. $B(N, N) = A(N, N)$
   последняя клетка обязательно входит в маршрут
2. $B(N, J) = B(N,J+1) + A (N, J)$ при $J = N-1, N-2, ... , 1$
   если маршрут вышел в последнюю строку таблицы, то он обязательно будет проходить до конца по последней строке, так как он кратчайший
3. $B(I, N) = B(I+1, N) + A (I, N)$ при $I = N-1, N-2, ..., 1$
   если маршрут вышел в последний столбец таблицы, то он обязательно будет проходить до конца по последнему столбцу
4. $B(I, J) = max (B(I+1, J),  B(I, J+1)) + A (I, J)$ при $I<N$ и $J<N$
   внутри таблицы в маршрут будет входить та клетка из последующего столбца или последующей строки, в которой сумма цифр больше

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

Программа .1:
RANDOMIZE TIMER
CLS
INPUT "Введите размерность N: "; n
DIM a(n, n), b(n, n)
FOR i = 1 TO n
FOR j = 1 TO n
a(i, j) = INT(RND * 10)
PRINT a(i, j);
NEXT j
PRINT
NEXT i
'Формирование дополнительной матрицы
b(n, n) = a(n, n)
FOR i = n - 1 TO 1 STEP -1
b(i, n) = b(i + 1, n) + a(i, n)
b(n, i) = b(n, i + 1) + a(n, i)
NEXT i
FOR i = n - 1 TO 1 STEP -1
FOR j = n - 1 TO 1 STEP -1
b(i, j) = max(b(i + 1, j), b(i, j + 1)) + a(i, j)
NEXT j, i
PRINT
PRINT "Сумма чисел на всем кратчайшем пути = "; b(1, 1)
'Путь ищется обратным проходом
PRINT "( 1; 1)";
i = 1: j = 1
WHILE (i <> n) OR (j <> n)
IF i = n THEN                                    'Если дошли до нижней границы
j = j + 1
ELSE
IF j = n THEN                       'Если дошли до правой границы
i = i + 1
ELSE
IF b(i + 1, j) > b(i, j + 1) THEN i = i + 1 ELSE j = j + 1
END IF
END IF
PRINT USING " - (##;##)"; i; j;
WEND

FUNCTION max (a, b)
IF a > b THEN max = a ELSE max = b
END FUNCTION

Задача 2. Акирема

(Областная олимпиада 1998).
В государстве Акирема алфавит состоит из букв американского языка. Каждый акиремец (житель) имеет право пополнить словарь своего языка новым словом.
Слово формируется по следующим правилам:

• Предлагается N известных слов (длина каждого слова не превосходит M);
• Слова выписываются друг под другом с выравниванием по левому краю;
• Из каждого слова выбирается по одной букве непрерывной цепочкой, т.е. буквы должны граничить друг с другом по вертикали или по диагонали;
• Полученное таким образом слово длины N должно иметь максимальную сумму кодов ASCII каждой буквы.

Какое новое слово может  сформировать акиремец по предложенным словам.

Примечание. Данные вводятся из файла с именем INPUT.TXT. В файле они заданы так: числа N и M – на первой строке через разделитель, каждое слово задаётся с новой строки.
Вывод осуществляется на экран или в файл с именем OUTPUT.TXT.

Пример: из слов
A P P L E
W I N D O W S
M O U S E
B Y T E

должно получиться слово PWOY.

Указание. Задача легко сводится к предыдущей. Строится матрица A размера NxM, где N – количество слов, а M – количество букв в самом длинном слове (табл. 1). Массив первоначально заполняется кодами ASCII букв каждого слова, расположенного в матрице по строкам с выравниванием по левой стороне (для коротких слов в матрице на местах отсутствия букв проставляются нули).

Таблица 1

Затем массив преобразуется по следующему правилу (табл. 2):

• последняя строка в матрице остается без изменений;
• начиная с предпоследней строки и до первой, считаем суммы только по допустимым продолжениям. Пустые позиции и буквы без цепочки до последнего слова не участвуют в максимуме:
• для существующей буквы с допустимым продолжением выполняются следующие переходы:
• A (I, J) = max (A (I+1, J), A (I+1, J+1)) + A (I, J) при I = N-1, N-2, …, 1 и J = 1
• A (I, J) = max (A (I+1, J), A (I+1, J-1)) + A (I, J) при I = N-1, N-2, …, 1 и J = M
• A (I, J) = max (A (I+1, J-1), A (I+1, J), A (I+1, J+1)) + A (I, J) при I = N-1, …, 1 и J = 2, 3, …, M-1.

Таблица 2

В первой строке матрицы ищется наибольший элемент – это и есть искомая максимальная сумма кодов ASCII. Обратным ходом, выбирая всегда наибольшее значение, необходимо двигаться сверху вниз (с первой строки до последней), составляя строку из соответствующих букв. Искомое слово найдено - PWOY.

Программа 2:

    DEFINT A-Z
    OPEN "input.txt" FOR INPUT AS #1
    INPUT #1, n, m
    DIM Word$(1 TO n), Marks(0 TO n, 0 TO m + 1)

FOR i = 1 TO n
    INPUT #1, Word$(i)
    FOR j = 1 TO LEN(Word$(i))
    Marks(i, j) = ASC(MID$(Word$(i), j, 1)) + max(Marks(i - 1, j - 1), _
    Marks(i - 1, j), Marks(i - 1, j + 1))
    NEXT
    NEXT

k = 1
    FOR i = 2 TO LEN(Word$(n))
    IF Marks(n, i) > Marks(n, k) THEN k = i
    NEXT

FOR i = n TO 1 STEP -1
    s$ = MID$(Word$(i), k, 1) + s$
    IF Marks(i - 1, k - 1) > Marks(i - 1, k + 1) THEN k = k - 1
    IF Marks(i - 1, k + 1) > Marks(i - 1, k) THEN k = k + 1
    NEXT
    PRINT s$

FUNCTION max (a, b, c)
    IF a > b THEN
    IF a > c THEN max = a ELSE max = c
    ELSE
    IF b > c THEN max = b ELSE max = c
    END IF
    END FUNCTION

Задача 3. INTERNETомания

(Районная олимпиада 1999)

Компания «Питерские сети» проводит подключение к сети INTERNET N-этажных домов. На каждом этаже компьютеры подключаются к концентратору (HUB) по топологии «звезда», т.е. каждый компьютер соединяется с концентратором отдельным кабелем (рис. 2).
Количество квартир на каждом этаже равно K (для упрощения предполагается, что квартиры расположены на одной прямой, и нумерация квартир идет слева направо). Расстояние между соседними квартирами и этажами одинаково. Схема дома представлена в виде прямоугольной таблицы, строки которой – этажи, а столбцы – квартиры. Квартиры, имеющие компьютер, обозначаются 1 (единицей), а остальные 0 (нулями). Переход с одного этажа на другой возможен только в ближайшие квартиры (рис. 3).

Требуется написать программу, которая выведет номера квартир, начиная с первого этажа, в которых должны быть расположены HUB’ы, при условии, что общая длина кабеля, соединяющего все компьютеры в сети, минимальна.

Примечание.  Концентраторы (HUB) могут располагаться и в тех квартирах, где нет компьютеров.

Формат входных данных:
Входные данные расположены в текстовом файле с именем INPUT.TXT в следующем порядке:

• первая строка содержит числа N (≤ 14) и K (≤ 8);
• последующие строки – это строки таблицы, состоящей из нулей и единиц и изображающей схему дома с компьютерами.

Формат выходных данных:
Результат работы программы выводится в файл OUTPUT.TXT и представляет собой последовательность номеров квартир, начиная с первого этажа, в которых должны располагаться концентраторы HUB.

Пример файла INPUT.TXT (рис. 4):

Строки файла: первая – числа $N$ и $K$; каждая следующая – этаж (от 5-го к 1-му), где 1 означает квартиру с компьютером, 0 – квартиру без компьютера.

  1
  5
  8
  12
  14 

Указание. Задача легко сводится к предыдущей.

Еще одно из сравнительно новых применений динамического программирования – молекулярная биология, где базы данных содержат биологические последовательности (ДНК, РНК, белков), насчитывающие в сумме многие миллионы «букв», так что в их анализе не обойтись без компьютеров. Молекулы ДНК, содержащие генетическую информацию, - это длинные слова из четырех букв (А, Г, Ц, Т). В процессе эволюции, в результате мутаций последовательности меняются: одна буква может замениться на другую, выпасть, а может добавиться новая. Возникают жизненно важные задачи: насколько похожи два фрагмента, каким наименьшим числом превращений можно один из них получить из другого, найти подпоследовательность наибольшей длины, входящую в тот или другой фрагмент.

Задача 4. Наибольшая общая подпоследовательность

Заданы два слова длиной N и M соответственно ($N, M \le 30$). Найти подпоследовательность максимальной длины, входящую в то и другое слово (подпоследовательность не обязана быть непрерывной).

Задачи на динамическое программирование

Числа Фибоначчи

Вычислить $N$-ое число в последовательности Фибоначчи, — 1, 1, 2, 3, 5, 8, … — в которой первые два члена равны единице, а все остальные представляют собой сумму двух предыдущих.
Входные данные: Целое: $1 \le N \le 70$.
Выходные данные: Одно число — $N$-ый член последовательности.

Решение: условие задачи в виде формулы (динамический переход): $F_1=1$, $F_2=1$, $F_i=F_{i-1}+F_{i-2}, i \ge 3$.

const MaxN = 70;
var i,N : Integer;
    F : Array [1..MaxN] of Int64; { Массив для хранения вычисленных значений F }
begin
  { Чтение входных данных }
  Read(N);
  { Проверка корректности входных данных (assert работает только с опцией -Sa) }
  assert( (1 <= N) and (N <= MaxN) );
  { Инициализация "динамики", первые 2 значения F }
  F[1]:=1;  F[2]:=1;
  { Общий шаг динамики: в цикле вычисляем значения F }
  for i:=3 to N do
    F[i] := F[i-1] + F[i-2];
  { Вывод результата }
  write(F[N]);
end.

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

# Числа Фибоначчи, динамика снизу вверх: O(N) по времени, O(N) по памяти.
# F(1) = F(2) = 1, F(i) = F(i-1) + F(i-2).


def fibonacci(n: int) -> int:
    # f[i] - i-е число Фибоначчи; f[0] в задаче не нужно, f[1] и f[2] - база динамики.
    f = [0, 1, 1]
    for i in range(3, n + 1):
        f.append(f[i - 1] + f[i - 2])
    return f[n]


def main() -> None:
    print(f"F(10) = {fibonacci(10)}")
    print(f"F(70) = {fibonacci(70)}")


if __name__ == "__main__":
    main()

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

// Числа Фибоначчи, динамика снизу вверх: O(N) по времени, O(N) по памяти.
#include <cstddef>
#include <cstdio>
#include <vector>

// N-е число Фибоначчи: F(1) = F(2) = 1, F(i) = F(i-1) + F(i-2).
unsigned long long fibonacci(std::size_t n) {
    // f[i] - i-е число; f[0] в задаче не нужно, f[1] и f[2] - база динамики.
    std::vector<unsigned long long> f = {0, 1, 1};
    for (std::size_t i = 3; i <= n; ++i) {
        f.push_back(f[i - 1] + f[i - 2]);
    }
    return f[n];
}

int main() {
    std::printf("F(10) = %llu\n", fibonacci(10));
    std::printf("F(70) = %llu\n", fibonacci(70));
    return 0;
}

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

// Числа Фибоначчи, динамика снизу вверх: O(N) по времени, O(N) по памяти.

/// N-е число Фибоначчи: F(1) = F(2) = 1, F(i) = F(i-1) + F(i-2).
pub fn fibonacci(n: usize) -> u64 {
    // f[i] - i-е число; f[0] в задаче не нужно, f[1] и f[2] - база динамики.
    let mut f: Vec<u64> = vec![0, 1, 1];
    for i in 3..=n {
        let next = f[i - 1] + f[i - 2];
        f.push(next);
    }
    f[n]
}

fn main() {
    println!("F(10) = {}", fibonacci(10));
    println!("F(70) = {}", fibonacci(70));
}

Мячик на лесенке

На вершине лесенки, содержащей $N$ ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.). Определить число всевозможных "маршрутов" мячика с вершины на землю.
Входные данные: Целое: $1 \le N \le 40$.
Выходные данные: Одно число — количество маршрутов.

Решение:
$D_i$ - количество всевозможных способов попасть на $i$-ую ступеньку.
$D_1=1$ - только один способ попасть на первую ступеньку.
$D_2=2$ - попасть на 2-ую можно 2-мя способами: прыгнув на неё сразу или прыгнув с 1-ой ступеньки.
$D_3=4$ - попасть на 3-ую можно 4-мя способами:
1) прыгнув на неё сразу
2) прыгнув на 1-ую, потом на 3-ю
3) прыгнув на 2-ую, потом на 3-ю
4) прыгнув на 1-ую ступеньку, потом на 2-ую, потом на 3-ю.
$D_i=D_{i-1}+D_{i-2}+D_{i-3}, i \ge 4$ - на ступеньки начиная с 4-ой можно попасть с 3-х предыдущих. Мы знаем, сколькими способами можно попасть на каждую ступеньку из предыдущих. Общий принцип: Количество вариантов как попасть в какое-то состояние равно сумме количеств вариантов как попасть в предыдущие состояния.

var I,N : integer;
    D : array [1..40] of Int64;
begin
  read(N);
  D[1]:=1; D[2]:=2; D[3]:=4;
  for I:=4 to N do
    D[I] := D[I-1] + D[I-2] + D[I-3];
  writeln(D[N])
end.

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

# Мячик на лесенке, динамика: D[i] = D[i-1] + D[i-2] + D[i-3], O(N) по времени и по памяти.
def ball_routes(n: int) -> int:
    # ways[i] - число способов попасть на ступеньку i (нумерация снизу вверх), ways[0] не используется.
    ways = [0, 1, 2, 4]  # базовые значения для первых трёх ступенек
    if n < len(ways):
        return ways[n]
    for i in range(4, n + 1):
        ways.append(ways[i - 1] + ways[i - 2] + ways[i - 3])
    return ways[n]


def main() -> None:
    for n in (4, 13, 39):
        print(f"N = {n}: маршрутов {ball_routes(n)}")


if __name__ == "__main__":
    main()

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

// Мячик на лесенке, динамика: D[i] = D[i-1] + D[i-2] + D[i-3], O(N) по времени и по памяти.
#include <cstddef>
#include <cstdio>
#include <vector>

// Число маршрутов мячика с вершины лесенки из n ступенек на землю.
unsigned long long ball_routes(std::size_t n) {
    // ways[i] - число способов попасть на ступеньку i (нумерация снизу вверх), ways[0] не используется.
    std::vector<unsigned long long> ways = {0, 1, 2, 4};  // базовые значения для первых трёх ступенек
    if (n < ways.size()) {
        return ways[n];
    }
    for (std::size_t i = 4; i <= n; ++i) {
        ways.push_back(ways[i - 1] + ways[i - 2] + ways[i - 3]);
    }
    return ways[n];
}

int main() {
    const std::size_t tests[] = {4, 13, 39};
    for (std::size_t n : tests) {
        std::printf("N = %zu: маршрутов %llu\n", n, ball_routes(n));
    }
    return 0;
}

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

// Мячик на лесенке, динамика: D[i] = D[i-1] + D[i-2] + D[i-3], O(N) по времени и по памяти.

/// Число маршрутов мячика с вершины лесенки из n ступенек на землю.
pub fn ball_routes(n: usize) -> u64 {
    // ways[i] - число способов попасть на ступеньку i (нумерация снизу вверх), ways[0] не используется.
    let mut ways: Vec<u64> = vec![0, 1, 2, 4]; // базовые значения для первых трёх ступенек
    if n < ways.len() {
        return ways[n];
    }
    for i in 4..=n {
        let next = ways[i - 1] + ways[i - 2] + ways[i - 3];
        ways.push(next);
    }
    ways[n]
}

fn main() {
    for n in [4, 13, 39] {
        println!("N = {}: маршрутов {}", n, ball_routes(n));
    }
}

Черепашка

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

Решение: $S_{ij}$ - максимальная набранная сумма, если черепашка находится в клетке $i,j$
Динамический переход: $S_{ij}=max(S_{i-1,j},S_{i,j-1})+A_{i,j}$
Инициализация: $S_{i,0} = 0$ $S_{0,j} = 0$
Ответ: $S_{N,N}$

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

# Черепашка, динамика по клеткам (ходы вправо и вниз): O(N^2) по времени и по памяти.
def max_path_sum(board: list[list[int]]) -> int:
    n = len(board)
    # best[i][j] - максимум суммы пути из (0, 0) в клетку (i, j), нумерация с 1.
    # Нулевые строка и столбец - граница; она не портит ответ, так как все числа неотрицательны.
    best = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            best[i][j] = max(best[i - 1][j], best[i][j - 1]) + board[i - 1][j - 1]
    return best[n][n]


def main() -> None:
    board = [
        [2, 6, 0],
        [5, 0, 6],
        [4, 1, 2],
    ]
    print(f"Максимальная сумма: {max_path_sum(board)}")


if __name__ == "__main__":
    main()

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

// Черепашка, динамика по клеткам (ходы вправо и вниз): O(N^2) по времени и по памяти.
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <vector>

// Максимальная сумма чисел на пути из левого верхнего угла в правый нижний.
long long max_path_sum(const std::vector<std::vector<long long>>& board) {
    const std::size_t n = board.size();
    // best[i][j] - максимум суммы пути в клетку (i, j), нумерация с 1.
    // Нулевые строка и столбец - граница; она не портит ответ, так как все числа неотрицательны.
    std::vector<std::vector<long long>> best(n + 1, std::vector<long long>(n + 1, 0));
    for (std::size_t i = 1; i <= n; ++i) {
        for (std::size_t j = 1; j <= n; ++j) {
            best[i][j] = std::max(best[i - 1][j], best[i][j - 1]) + board[i - 1][j - 1];
        }
    }
    return best[n][n];
}

int main() {
    const std::vector<std::vector<long long>> board = {
        {2, 6, 0},
        {5, 0, 6},
        {4, 1, 2},
    };
    std::printf("Максимальная сумма: %lld\n", max_path_sum(board));
    return 0;
}

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

// Черепашка, динамика по клеткам (ходы вправо и вниз): O(N^2) по времени и по памяти.

/// Максимальная сумма чисел на пути из левого верхнего угла в правый нижний.
pub fn max_path_sum(board: &[Vec<u64>]) -> u64 {
    let n = board.len();
    // best[i][j] - максимум суммы пути в клетку (i, j), нумерация с 1.
    // Нулевые строка и столбец - граница; она не портит ответ, так как все числа неотрицательны.
    let mut best = vec![vec![0u64; n + 1]; n + 1];
    for i in 1..=n {
        for j in 1..=n {
            best[i][j] = best[i - 1][j].max(best[i][j - 1]) + board[i - 1][j - 1];
        }
    }
    best[n][n]
}

fn main() {
    let board: Vec<Vec<u64>> = vec![vec![2, 6, 0], vec![5, 0, 6], vec![4, 1, 2]];
    println!("Максимальная сумма: {}", max_path_sum(&board));
}

Робот

В исследовательской лаборатории фирмы Robots&Co разработали новую модель робота. Главной особенностью данной модели робота является то, что он работает по заранее заданной программе, в которой могут присутствовать команды: сделать шаг на Юг, на Север, на Восток или на Запад. Робот исполняет программу строго последовательно и, дойдя до конца программы, останавливается. Специалисты из Robots&Co заинтересовались вопросом, сколько существует различных программ, состоящих из K инструкций, таких, что робот, выйдя из начала координат, придет в точку с координатами (X, Y). Оси координат располагаются параллельно сторонам света, и единица измерения, соответствует одному шагу робота. Напишите программу, которая дает ответ на этот вопрос.
Входные данные:
Во входном файле находятся три числа K, X и Y ($0 \le K \le 16, |X|, |Y| \le 16$), разделенные пробелами.
Выходные данные:
В выходной файл ваша программа должна поместить одно число — количество программ для робота.

Решение:

$W_{KXY}$ - количество программ для робота состоящих из $K$ инструкций, таких, что робот, выйдя из начала координат, придет в точку с координатами $(X, Y)$

$W_{0XY} = 0$ при $(X, Y) \ne (0, 0)$

$W_{000} = 1$ - в начальную клетку робот может попасть 1 способом.

Общий шаг: $W_{KXY} = W_{K-1,X-1,Y} + W_{K-1,X+1,Y} + W_{K-1,X,Y-1} + W_{K-1,X,Y+1}$

$Answer = W_{KXY}$

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

# Робот: число программ из k команд, приводящих в точку (x, y). Динамика по числу команд: O(k^3) по времени, O(k^2) по памяти.

# Команды робота: шаг на восток, на запад, на север и на юг.
STEPS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def robot_programs(k: int, x: int, y: int) -> int:
    # ways[(a, b)] - число программ длины i, после которых робот стоит в точке (a, b).
    # При i = 0 робот стоит в начале координат, и есть одна пустая программа.
    ways = {(0, 0): 1}
    for _ in range(k):
        # Каждая программа длины i продолжается одной командой и даёт программу длины i + 1.
        next_ways: dict[tuple[int, int], int] = {}
        for (a, b), count in ways.items():
            for dx, dy in STEPS:
                cell = (a + dx, b + dy)
                next_ways[cell] = next_ways.get(cell, 0) + count
        ways = next_ways
    return ways.get((x, y), 0)


def main() -> None:
    print(f"K = 5, X = -2, Y = -3: {robot_programs(5, -2, -3)}")
    print(f"K = 16, X = 16, Y = 15: {robot_programs(16, 16, 15)}")
    print(f"K = 16, X = 3, Y = 3: {robot_programs(16, 3, 3)}")


if __name__ == "__main__":
    main()

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

// Робот: число программ из k команд, приводящих в клетку (x, y). Динамика по числу команд: O(k^3 log k) по времени, O(k^2) по памяти.
#include <cstdio>
#include <map>
#include <utility>

// Сдвиги команд: восток, запад, север, юг.
const int kDx[4] = {1, -1, 0, 0};
const int kDy[4] = {0, 0, 1, -1};

// Число программ длины k, после которых робот стоит в клетке (x, y).
unsigned long long robot_programs(int k, int x, int y) {
    // ways[{a, b}] - число программ длины i, после которых робот стоит в клетке (a, b).
    std::map<std::pair<int, int>, unsigned long long> ways = {{{0, 0}, 1}};
    for (int step = 0; step < k; ++step) {
        // Каждая программа длины step продолжается одной командой и даёт программу длины step + 1.
        std::map<std::pair<int, int>, unsigned long long> next;
        for (const auto& [cell, count] : ways) {
            for (int d = 0; d < 4; ++d) {
                next[{cell.first + kDx[d], cell.second + kDy[d]}] += count;
            }
        }
        ways = std::move(next);
    }
    const auto found = ways.find({x, y});
    return found == ways.end() ? 0 : found->second;
}

int main() {
    std::printf("K = 5, X = -2, Y = -3: %llu\n", robot_programs(5, -2, -3));
    std::printf("K = 16, X = 16, Y = 15: %llu\n", robot_programs(16, 16, 15));
    std::printf("K = 16, X = 3, Y = 3: %llu\n", robot_programs(16, 3, 3));
    return 0;
}

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

// Робот: число программ из k команд, приводящих в клетку (x, y). Динамика по числу команд: O(k^3) по времени, O(k^2) по памяти.
use std::collections::HashMap;

/// Сдвиги команд: восток, запад, север, юг.
const STEPS: [(i32, i32); 4] = [(1, 0), (-1, 0), (0, 1), (0, -1)];

/// Число программ длины k, после которых робот стоит в клетке (x, y).
pub fn robot_programs(k: usize, x: i32, y: i32) -> u64 {
    // ways[(a, b)] - число программ длины i, после которых робот стоит в клетке (a, b).
    let mut ways: HashMap<(i32, i32), u64> = HashMap::new();
    ways.insert((0, 0), 1);
    for _ in 0..k {
        // Каждая программа длины i продолжается одной командой и даёт программу длины i + 1.
        let mut next: HashMap<(i32, i32), u64> = HashMap::new();
        for (&(a, b), &count) in &ways {
            for (dx, dy) in STEPS {
                *next.entry((a + dx, b + dy)).or_insert(0) += count;
            }
        }
        ways = next;
    }
    ways.get(&(x, y)).copied().unwrap_or(0)
}

fn main() {
    println!("K = 5, X = -2, Y = -3: {}", robot_programs(5, -2, -3));
    println!("K = 16, X = 16, Y = 15: {}", robot_programs(16, 16, 15));
    println!("K = 16, X = 3, Y = 3: {}", robot_programs(16, 3, 3));
}

Взрывоопасность

При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры, последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более двух контейнеров типа A. Для заданного количества контейнеров N определить число безопасных стопок.
Входные данные:
Одно число $1 \le N \le 30$.
Выходные данные:
Одно число — количество безопасных вариантов формирования стопки.

Решение:

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

# Взрывоопасность: число безопасных стопок из n контейнеров (без трёх контейнеров A подряд). Динамика: O(n) по времени, O(1) по памяти.


def safe_stacks(n: int) -> int:
    # Состояние стопки - сколько контейнеров A стоит сверху подряд: 0, 1 или 2 (три подряд - взрывоопасно, не считаем).
    # no_a - стопки без A сверху (в том числе пустая), one_a - с одной A сверху, two_a - с двумя A сверху.
    no_a, one_a, two_a = 1, 0, 0
    for _ in range(n):
        # Контейнер B сводит счётчик A к нулю, контейнер A увеличивает его на единицу.
        no_a, one_a, two_a = no_a + one_a + two_a, no_a, one_a
    return no_a + one_a + two_a


def main() -> None:
    for n in range(1, 6):
        print(f"N = {n}: безопасных стопок {safe_stacks(n)}")
    print(f"N = 30: безопасных стопок {safe_stacks(30)}")


if __name__ == "__main__":
    main()

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

// Взрывоопасность: число безопасных стопок из n контейнеров (без трёх контейнеров A подряд). Динамика: O(n) по времени, O(1) по памяти.
#include <cstdio>

// Число безопасных стопок из n контейнеров.
unsigned long long safe_stacks(int n) {
    // no_a - стопки без A сверху (в том числе пустая), one_a - с одной A сверху, two_a - с двумя A сверху.
    unsigned long long no_a = 1;
    unsigned long long one_a = 0;
    unsigned long long two_a = 0;
    for (int i = 0; i < n; ++i) {
        // Контейнер B сводит счётчик A к нулю, контейнер A увеличивает его на единицу.
        const unsigned long long after_b = no_a + one_a + two_a;
        two_a = one_a;
        one_a = no_a;
        no_a = after_b;
    }
    return no_a + one_a + two_a;
}

int main() {
    for (int n = 1; n <= 5; ++n) {
        std::printf("N = %d: безопасных стопок %llu\n", n, safe_stacks(n));
    }
    std::printf("N = 30: безопасных стопок %llu\n", safe_stacks(30));
    return 0;
}

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

// Взрывоопасность: число безопасных стопок из n контейнеров (без трёх контейнеров A подряд). Динамика: O(n) по времени, O(1) по памяти.

/// Число безопасных стопок из n контейнеров.
pub fn safe_stacks(n: usize) -> u64 {
    // no_a - стопки без A сверху (в том числе пустая), one_a - с одной A сверху, two_a - с двумя A сверху.
    let (mut no_a, mut one_a, mut two_a) = (1u64, 0u64, 0u64);
    for _ in 0..n {
        // Контейнер B сводит счётчик A к нулю, контейнер A увеличивает его на единицу.
        (no_a, one_a, two_a) = (no_a + one_a + two_a, no_a, one_a);
    }
    no_a + one_a + two_a
}

fn main() {
    for n in 1..=5 {
        println!("N = {}: безопасных стопок {}", n, safe_stacks(n));
    }
    println!("N = 30: безопасных стопок {}", safe_stacks(30));
}

К-ичные числа

Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких, что их запись не содержит двух подряд идущих нулей. ($2 \le K \le 10, N + K \le 18$).
Входные данные:
Числа N и K в десятичной записи, разделенные пробелом или переводом строки.
Выходные данные:
Искомое число в десятичной записи.

Решение:

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

# К-ичные числа: число n-значных записей в основании k без двух нулей подряд. Динамика по последней цифре: O(n) по времени, O(1) по памяти.


def k_ary_numbers(n: int, k: int) -> int:
    if n == 0:
        return 0
    # zero_end - записи длины i, оканчивающиеся нулём; digit_end - оканчивающиеся ненулевой цифрой.
    # Первая цифра не может быть нулём: для длины 1 есть k - 1 записей, все оканчиваются ненулевой цифрой.
    zero_end, digit_end = 0, k - 1
    for _ in range(n - 1):
        # Ноль можно дописать только после ненулевой цифры, ненулевую (k - 1 вариант) - после любой записи.
        zero_end, digit_end = digit_end, (k - 1) * (zero_end + digit_end)
    return zero_end + digit_end


def main() -> None:
    print(f"N = 4, K = 3: {k_ary_numbers(4, 3)}")
    print(f"N = 5, K = 2: {k_ary_numbers(5, 2)}")
    print(f"N = 8, K = 10: {k_ary_numbers(8, 10)}")


if __name__ == "__main__":
    main()

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

// К-ичные числа: число n-значных записей в основании k без двух нулей подряд. Динамика по последней цифре: O(n) по времени, O(1) по памяти.
#include <cstdio>

// Число n-значных записей в основании k без двух нулей подряд (первая цифра не ноль).
unsigned long long k_ary_numbers(int n, int k) {
    if (n == 0) {
        return 0;
    }
    const auto nonzero = static_cast<unsigned long long>(k - 1);  // ненулевых цифр в основании k
    // zero_end - записи длины i, оканчивающиеся нулём; digit_end - оканчивающиеся ненулевой цифрой.
    unsigned long long zero_end = 0;
    unsigned long long digit_end = nonzero;  // длина 1: первая цифра ненулевая
    for (int i = 1; i < n; ++i) {
        // Ноль ставим только после ненулевой цифры, ненулевую - после любой записи.
        const unsigned long long next_zero_end = digit_end;
        digit_end = nonzero * (zero_end + digit_end);
        zero_end = next_zero_end;
    }
    return zero_end + digit_end;
}

int main() {
    std::printf("N = 4, K = 3: %llu\n", k_ary_numbers(4, 3));
    std::printf("N = 5, K = 2: %llu\n", k_ary_numbers(5, 2));
    std::printf("N = 8, K = 10: %llu\n", k_ary_numbers(8, 10));
    return 0;
}

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

// К-ичные числа: число n-значных записей в основании k без двух нулей подряд. Динамика по последней цифре: O(n) по времени, O(1) по памяти.

/// Число n-значных записей в основании k без двух нулей подряд (первая цифра не ноль).
pub fn k_ary_numbers(n: usize, k: u64) -> u64 {
    if n == 0 {
        return 0;
    }
    let nonzero = k - 1; // ненулевых цифр в основании k
    // zero_end - записи длины i, оканчивающиеся нулём; digit_end - оканчивающиеся ненулевой цифрой.
    let (mut zero_end, mut digit_end) = (0u64, nonzero); // длина 1: первая цифра ненулевая
    for _ in 1..n {
        // Ноль ставим только после ненулевой цифры, ненулевую - после любой записи.
        (zero_end, digit_end) = (digit_end, nonzero * (zero_end + digit_end));
    }
    zero_end + digit_end
}

fn main() {
    println!("N = 4, K = 3: {}", k_ary_numbers(4, 3));
    println!("N = 5, K = 2: {}", k_ary_numbers(5, 2));
    println!("N = 8, K = 10: {}", k_ary_numbers(8, 10));
}

Паровозики

N локомотивов, имеющих номера от 1 до N и установленных на железнодорожную колею, начинают двигаться в одну сторону, причем локомотив номер k изначально движется со скоростью k км/ч. Если локомотив, движущийся с большей скоростью, нагоняет более медленный локомотив, дальше они движутся один за другим со скоростью впереди идущего локомотива. Очевидно, через некоторое время после начала движения локомотивы разобьются на несколько групп, движущихся с разной скоростью.
Написать программу, определяющую, сколько начальных расстановок s из N! возможных дадут в результате p групп движущихся локомотивов.
Входные данные:
Два числа — $1 \le N \le 16$ и $1 \le p \le N$.
Выходные данные:
Одно число — s.

Самый быстрый паровозик n либо ставится впереди всех и образует новую группу, либо ставится позади одного из n − 1 остальных и число групп сохраняется. Эти два случая дают слагаемые динамического перехода.

uses SysUtils;

const Nmax=16;

var
  Save : array [1..nmax,1..nmax,1..nmax] of Int64;

function F( i,n,p:byte; x:integer ):Int64;
{ i-ый паровоз впереди,
  n паровозов всего
  p групп }
var j:byte;
begin
  if Save[i,n,p]=-1 then begin
    if x=0 then writeln( Format('F(i=%d,n=%d,p=%d)=',[i,n,p] ) );
    Result := 0;
    { Рассмотрим, как может i-ый паровозик оказаться впереди }
    { При этом есть 2 варианта: }
    {  1. Он уйдёт вперёд и образует новую группу }
    {    Т.е. он быстрее предыдущего паровозика }
    {    Пусть предыдущий едет со скоростью j }
    { Мы могли получить это из ситуации:
       j in [1..i-1]
       n-1 паровоз всего;
       p-1 группа всего;
       т.е. новый паровоз образовал новую группу }
    for j:=1 to i-1 do begin
      Result := Result + F(j,n-1,p-1,x+1);
      if x = 0 then writeln( Format('  + F(i=%d,n=%d,p=%d)=%d',[j,n-1,p-1,F(j,n-1,p-1,x+1)] ) );
    end;
    {   i-ый не образует новую группу, т.е. j>i }
    for j:=i+1 to n do begin
      Result := Result + F(i,n-1,p,x+1);
      if x = 0 then writeln( Format('  + F(i=%d,n=%d,p=%d)=%d *',[i,n-1,p,F(i,n-1,p,x+1)] ) );
    end;
    Save[i,n,p] := Result;
  end;
  F:=Save[i,n,p];
  if (i>n) or (p>n) then
    assert( Result = 0 );
end;

var i,j,NN,PP,n,p:byte;
    s:Int64;
begin
  readln(NN,PP);
  for i:=1 to NN do
    for n:=1 to NN do
      for p:=1 to NN do begin
        Save[i,n,p]:=-1;
        if (i>n) or (p>n) then Save[i,n,p]:=0;
        { Одна группа - и не первый впереди - не может быть :) }
        if (p=1) and (i<>1) then Save[i,n,p]:=0;
        { Кол-во групп = кол-ву паровозов и первый - самый быстрый }
        if (n=p) and (i=n) then Save[i,n,p]:=1;
      end;
  for i:=1 to NN do
    for n:=1 to NN do
      for p:=1 to NN do begin
        if (n=p) and (i<n) then assert( F(i,n,p,1) = 0 );
        if i>n then assert( F(i,n,p,1) = 0,
          Format('F(%d,%d,%d)=%d',[i,n,p,F(i,n,p,1)]) );
      end;
  s:=0;
  for i:=1 to NN do
    s:=s+F(i,NN,PP,1);
  writeln(s);
end.

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

# Паровозики: число расстановок n локомотивов, дающих groups групп (числа Стирлинга первого рода). Динамика: O(n^2) по времени и по памяти.
# c(i, k) = c(i - 1, k - 1) + (i - 1) * c(i - 1, k): самый быстрый локомотив либо первый и образует новую группу,
# либо стоит за одним из i - 1 локомотивов и не меняет число групп.


def locomotive_arrangements(n: int, groups: int) -> int:
    if not 0 <= groups <= n:
        return 0
    # stirling[i][k] - число расстановок i локомотивов по k группам.
    stirling = [[0] * (n + 1) for _ in range(n + 1)]
    stirling[0][0] = 1
    for i in range(1, n + 1):
        for k in range(1, i + 1):
            stirling[i][k] = stirling[i - 1][k - 1] + (i - 1) * stirling[i - 1][k]
    return stirling[n][groups]


def main() -> None:
    print(f"N = 4, p = 2: {locomotive_arrangements(4, 2)}")
    print(f"N = 5, p = 4: {locomotive_arrangements(5, 4)}")
    print(f"N = 6, p = 6: {locomotive_arrangements(6, 6)}")
    print(f"N = 16, p = 1: {locomotive_arrangements(16, 1)}")


if __name__ == "__main__":
    main()

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

// Паровозики: число расстановок n локомотивов, дающих groups групп (числа Стирлинга первого рода). Динамика: O(n^2) по времени и по памяти.
#include <cstddef>
#include <cstdio>
#include <vector>

// stirling[i][k] = c(i, k): число расстановок i локомотивов по k группам.
// c(i, k) = c(i - 1, k - 1) + (i - 1) * c(i - 1, k): самый быстрый локомотив либо первый и образует группу,
// либо стоит за одним из i - 1 локомотивов и не меняет число групп.
unsigned long long locomotive_arrangements(std::size_t n, std::size_t groups) {
    if (groups > n) {
        return 0;
    }
    std::vector<std::vector<unsigned long long>> stirling(n + 1, std::vector<unsigned long long>(n + 1, 0));
    stirling[0][0] = 1;
    for (std::size_t i = 1; i <= n; ++i) {
        for (std::size_t k = 1; k <= i; ++k) {
            stirling[i][k] = stirling[i - 1][k - 1] + static_cast<unsigned long long>(i - 1) * stirling[i - 1][k];
        }
    }
    return stirling[n][groups];
}

int main() {
    std::printf("N = 4, p = 2: %llu\n", locomotive_arrangements(4, 2));
    std::printf("N = 5, p = 4: %llu\n", locomotive_arrangements(5, 4));
    std::printf("N = 6, p = 6: %llu\n", locomotive_arrangements(6, 6));
    std::printf("N = 16, p = 1: %llu\n", locomotive_arrangements(16, 1));
    return 0;
}

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

// Паровозики: число расстановок n локомотивов, дающих groups групп (числа Стирлинга первого рода). Динамика: O(n^2) по времени и по памяти.

/// c(i, k) = c(i - 1, k - 1) + (i - 1) * c(i - 1, k): самый быстрый локомотив либо первый и образует группу,
/// либо стоит за одним из i - 1 локомотивов и не меняет число групп.
pub fn locomotive_arrangements(n: usize, groups: usize) -> u64 {
    if groups > n {
        return 0;
    }
    // stirling[i][k] - число расстановок i локомотивов по k группам.
    let mut stirling = vec![vec![0u64; n + 1]; n + 1];
    stirling[0][0] = 1;
    for i in 1..=n {
        for k in 1..=i {
            stirling[i][k] = stirling[i - 1][k - 1] + ((i - 1) as u64) * stirling[i - 1][k];
        }
    }
    stirling[n][groups]
}

fn main() {
    println!("N = 4, p = 2: {}", locomotive_arrangements(4, 2));
    println!("N = 5, p = 4: {}", locomotive_arrangements(5, 4));
    println!("N = 6, p = 6: {}", locomotive_arrangements(6, 6));
    println!("N = 16, p = 1: {}", locomotive_arrangements(16, 1));
}