Основные этапы решения задачи на динамическое программирование при помощи Top-Down подхода

Если в формулировке задачи присутствуют фразы типа "найти число способов...", "максимальное/минимальное число ...", "используя самую выгодную стратегию.." и т.д. Или вы видите какие-то ветвления в задаче. Это хорошие индикаторы, что это задача на динамическое программирование.

В целом динамическое программирование это "умный перебор".

В Top-down подходе есть четыре ключевых шага в решении:

1) Составить рекурсивное выражение. Чтобы это сделать, посмотрите, какие есть ветвления в задаче. В задаче про лестницу: шаги на 1, 2, 3 ступеньки. В задаче про размен монет: будем ли использовать на текущем шагу монету определенного номинала или нет. Далее нужно что-то сделать с результатами рекурсивных вызовов, чтобы получить финальный результат. В задачах про "число способов" это обычно сумма. В задачах на минимальное, оптимальное и т.д. Обычно это какие-то минимумы или максимумы. В задаче про лестницу это сумма: f(n) = f(n-1) + f(n-2) + f(n-3).
2) Найти base-cases. Чтобы у вас рекурсия была не бесконечной, ее нужно где-то прервать. Для чисел Фибоначчи это f(0) = 1, f(1) = 1. Для лестницы это n<0 -> 0, n==0 -> 1. Обычно, это значения для нулевых или отрицательных значений. Обычно, они равны 1 или 0. Не всегда, конечно, все зависит от задачи. Но чаще всего так. Иногда это может быть плюс или минус бесконечность, особенно в задачах, где нужно работать с минимумами или максимумами.
3) Написать код решения.
4) Добавить кэш (мемоизацию). Это позволяет резко сократить количество вычислений. Кэш позволяет хранить уже вычисленные ранее значения.