Рассмотрим простую задачу на динамическое программирование, в которой построение ответа почти в два раза больше, чем само решение. Читаем условие: Задача не является продолжением или вариацией задачи 16. Лесенка, но решать будем тоже с помощью динамики. Считаем входные данные и сразу преобразуем их к числовым типам: Состоянием в динамическом программировании будет номер ступеньки, на которой стоит Вова. Чтобы узнать переходы, надо ответить на вопрос "Как Вова мог здесь оказаться?". Ответ очень простой - или с предыдущей ступеньки или через одну от неё...

Я не знаю, как обстоят дела в образовании сейчас, но 10-15 лет назад ни в школе, ни в университете никто всерьёз не объяснял, что программирование имеет свои типы, каждый из которых требует особого типа мышления. Не то чтобы это покалечило чьи-то судьбы, но изучение программных дисциплин могло бы проходить гораздо быстрее, если на стадии закладки фундамента мы представили многообразие языков и подходов, а не зомбически учили C++ в его консольных проявления. Многие, сталкиваясь с необходимостью...