Поднимаясь по лестнице, заяц прыгает либо на следующую ступеньку, либо через одну, либо через две. Сколькими способами он может поднятся на ступеньку с номером K?
Всё вроде бы понятно...
#include <iostream>
using namespace std;
int vr(int n)
{
if (n<3) return n;
else if (n==3) return 4;
else return vr(n-1)+vr(n-2)+vr(n-3);
}
int main()
{
int n;
cin >> n;
cout << vr(n);
return 0;
}
Но когда программа не прошла тест по времени на 32 ступеньках, до меня наконец дошло, что такой алгоритм порождает немеренное количество повторяемых вычислений, тем самым растрачивая драгоценные ресурсы. Прошу мудрые головы натолкнуть на мысль истинную, как же сократить количество вычислений заоблачное до количества оптимального.
n
и пройти по нему циклом. Вариант получше: т. к. мы используем только 3 последних элемента, достаточно создать массив всего из трех элементов и проходить по нему несколько раз.