Задача “Цветочный магазин” (Рекуррентное соотношение с двумя параметрами)

Условие задачи: ссылка
Основная идея: Данная задача была представлена на IOI’99. Разбор этой задачи можно найти в первой книги Михаила Долинского и в  “Методике решения задач по информатике”. Рекомендую ознакомится.
Пусть f(i,j) – максимальная эстетическая ценность размещения i букетов по j вазам.
Рассмотри первоначальная таблицу a:

Задача “Двоичные числа” (Рекуррентное соотношение с одним параметром )

Условие задачи: ссылка
Основная идея: Чтобы прочувствовать решение задачи предлагаю начать с более простого случая, когда K=2. Обозначим K(n) – количество n битных чисел без 2-ых подряд идущих единиц. K(1) = 2 – факт очевидный. Найдем решение для n=2. На вторую позицию можно поставить либо ноль, либо единицу. Ноль можно ставить смело, а вот единица может образовать запрещенную комбинацию, если на первой позиции также стояла единица. Проанализируем таблицу:

Задача “Треугольник” (Рекуррентное соотношение с двумя параметрами)

Условие задачи: ссылка
Основная идея:  Данная задача является интерпретацией классической задачи “Черепашка”. Сначала давайте разберемся как будем хранить наш дивный треугольник в памяти. По условию задачи он выглядит так:
          7
        3   8
      8   1   0
    2   7   4   4
  4   5   2   6   5
Нам бы хотелось иметь более дружественный вид. Например в виде матрицы:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Задача “Видеосалон” (Рекуррентное соотношение с одним параметром)

Условие задачи: ссылка
Основная идея:  Для успешного решения задачи было бы неплохо знать подход к решению классической задачи “Рюкзак” на Динамическое программирование. Все решение сводится к заполнению трех массивов: s,ns,ms (авторские названия).
Массив s:
s[i] == 1, если можно набрать суммарное время i, используя один или несколько фильмов.
s[i] == 0, в противном случае.
Массив ns:
ns[i] – количество способов, которыми можно набрать суммарное время i одним или несколькими фильмами. ns[i] не равен нулю только в том случае, если s[i] не равно нулю.
Массив ms:
ms[i] == 1, если время i было промежуточным для получения бОльшего времени I.
ms[i] == 0, в противном случае.

Исходный код: здесь

P.S: Признаюсь долго приходило понимание решения этой задачи. Основные моменты: строка 35 и способ формирования ответа.

Задача “Отбор в разведку” (Рекуррентное соотношение с одним параметром)

Условие задачи: ссылка
Основная идея:  Обозначим K(N) – ответ на задачу, а именно количество групп из 3 человек, которых можно послать в разведку из первоначальных N человек. Определим терминальное условие: K(1) = 0; K(2) = 0; K(3) = 1. Теперь рассмотрим шеренгу солдат для N=6 и N=7. Пусть N будет равно 6. Занумеруем солдат слева направо в порядке возрастания:

Полная шеренга(N=6):	1 2 3 4 5 6
Только четные:	2 4 6
Только нечетные:	1 3 5

Полная шеренга (N=7)	1 2 3 4 5 6 7
Только четные:	2 4 6
Только нечетные:	1 3 5 7

Вывод можно сделать однозначный. Если N-четное, то K(N) = K(N/2) + K(N/2) = 2*K(N/2).  В качестве первого слагаемого была шеренга, составленная из четных солдат, в качестве второго – из нечетных. Т.е. K(6) = 2*K(3) = 2*1 = 2.
Если N-нечетное, то можно формулу можно записать так: K(N) = K(N/2) + K(N-N/2). Слагаемые такие же и в первом случае. Т.е. K(7)= K(3) + K(4) = K(3) + K(2) + K(2) = 1 + 0 + 0 = 1.
Справедливости ради стоит заметить, что формула полученная для нечетного N также работает и для четного N.
Исходный код: здесь