Объясните это динамическое программирование, взбираясь по кодам

algorithm dynamic-programming

8382 просмотра

1 ответ

Проблема в

«Вы забираетесь на лестницу. Каждый раз вы можете сделать 1 или 2 шага. Лестница имеет 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;
 }

Спасибо,

Автор: Deepesh M Источник Размещён: 12.11.2019 09:12

Ответы (1)

11 плюса

Решение

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

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

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

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

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

Автор: amit Размещён: 30.03.2013 05:38
Вопросы из категории :
32x32