Задача про кузнечика и столбики. Почему рекурентная формула дает правильный ответ?
Смотрел разбор задачи про кузнечика, который может прыгать по столбикам только на один шаг или на два шага вперед. В задаче спрашивается, сколько всего существует способов допрыгать до i-ого столбика. В итоге формула получается такая:
d[n] = d[n-1] + d[n-2], что по сути и есть формула задающая последовательность чисел Фибоначчи F(n) = F(n-1) + F(n-2)
Что не могу понять, так это то, почему эта формула дает правильный ответ.
К примеру, если вычисляем d[4], то будет d[3] + d[2] = 5 способов допрыгать до четвертого столбика. Но ведь мы уже для d[3] учли d[2], зачем же еще раз d[3] складывать с d[2]?
