Одномерное динамическое программирование
На подвесном мосту на первой доске стоит Ваня Кобец. Всего мост состоит из 61 доски пронумерованных от -30 до 30. Ваня может либо шагнуть на 3 доски вперед, либо на 4 доски назад, то есть он совершает ходы
- Прибавь 3
- Вычти 4
При этом после каждого шага Вани предыдущая доска ломается и падает в пропасть, поэтому Ваня не может наступать на одну доску дважды. Первая команда увеличивает номер доски на 3, вторая уменьшает на 4. Сколько существует вариантов у Вани добраться с доски под номером 1 до доски под номером 20, при условии, что сходить с моста он не может.