Объясните это динамическое программирование, восходящее к n-лестничному коду

Проблема

"Вы поднимаетесь по лестнице, каждый раз, когда вы можете сделать один шаг или два шага. Лестница имеет n шагов. Сколько раз вы можете подняться по лестнице?"

Ниже приведено решение кода для этой проблемы, но у меня возникли проблемы с его пониманием. Может кто-нибудь объяснить мне

int stairs(int n) {
  if (n == 0) return 0;
  int a = 1;
  int b = 1;
  for (int i = 1; i < n; i++) {
    int c = a;
    a = b;
    b += c;
  }
  return b;
 }

Спасибо,

Ответы

Ответ 1

Ну, сначала вам нужно понять рекурсивную формулу и как мы вывели из нее итеративную версию.

Рекурсивная формула:

f(n) = f(n-1) + f(n-2)
f(0) = f(1) = 1

(f(n-1) за один шаг, f(n-2) для двух шагов, а общее число - это количество способов использования одной из этих опций - таким образом, суммирование).

Если вы внимательно посмотрите - это также известная серия - число фибоначчи, и решение просто вычисляет каждое число buttom-up вместо пересчета рекурсия снова и снова, что приводит к значительно более эффективному решению.