Грязные трюки: кеширование
- Разбор задач.
- Понятие кеша. Снижение вычислительной сложности при введении кеша
Разбор работы кеширующей функции на примере «задачи о распиле брёвен»
- Связь задач, оптимизируемых с помощью кеша, и динамического программирования
Домашнее задание
Задач эффективно решаемых именно кешированием, я не придумал 
. Похоже, это всегда такой костыль вместо динамического разбиения на подзадачи.
Почитать о кешировании в Википедии. Какое отношение это может иметь к решению сложных задач? MCCME Прямоугольники. Дан прямоугольник N×M, состоящий из квадратиков 1 ´ 1. Некоторые квадратики вырезали. Надо найти наименьшее количество прямоугольников, на которое можно разрезать оставшуюся фигуру.
Формат входных данных. В первой строке входных данных заданы числа N и M, (1 ≤ N, M ≤ 10). Далее следует N строк. В (i+1)-ой содержится M чисел; j-е число равно 1, если клетку на i-й строке и в j-м столбце вырезали из доски, 0 – если оставили.
Формат выходных данных. Выведите единственное число – минимальное количество прямоугольников, на которое можно разрезать полученную фигуру.
MCCME. Пилообразные последовательности. Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам n и k определите число пилообразных последовательностей длины n, составленных из чисел 1..k. Программа получает на вход два натуральных числа n и k, не превосходящих 106.
Условные обозначения
— тема по Linux 
— тема повышенной сложности - — теоретическое задание
— тема для самостоятельного изучения