Объясните это динамическое программирование, взбираясь по кодам
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Вопросы из категории :
- algorithm Функция для создания цветовых колес
- algorithm Big O, как вы рассчитываете / приближаете это?
- algorithm Пиковое обнаружение измеренного сигнала
- algorithm Головоломка: Найти самый большой прямоугольник (проблема максимального прямоугольника)
- algorithm Объединить Сортировать связанный список
- algorithm Алгоритм нахождения наибольшего простого множителя числа
- algorithm Алгоритм сравнения двух изображений
- algorithm Как я могу измерить сходство между двумя изображениями?
- algorithm Рассчитать расстояние между двумя точками широты и долготы? (Формула Haversine)
- algorithm Как обнаружить дубликаты данных?
- dynamic-programming Что такое динамическое программирование?
- dynamic-programming Как определить самую длинную возрастающую подпоследовательность с помощью динамического программирования?
- dynamic-programming Динамическое программирование - решение об изменении монет
- dynamic-programming Замена монет с ограниченным количеством монет
- dynamic-programming Longest common subsequence of 3+ strings
- dynamic-programming What is the difference between bottom-up and top-down?
- dynamic-programming Parenthesizing a string so that expression takes a given value
- dynamic-programming Максимальная последовательность увеличения веса
- dynamic-programming SPOJ АЛЬФА-КОД
- dynamic-programming Объясните это динамическое программирование, взбираясь по кодам