————————————
тема:
Есть высота10Лестница со ступенями, идите снизу вверх, каждая ступенька может идти только вверх1уровень или2шаги. Попросите программу узнать, сколько ходов.
Например, делать каждый раз по 1 шагу, всего делать 10 шагов, это один из способов ходьбы. Мы можем сократить его как 1,1,1,1,1,1,1,1,1,1.
Другой пример: каждый раз делайте по 2 шага, всего 5 шагов, что является еще одним способом ходьбы. Мы можем сократить его как 2,2,2,2,2.
Конечно, есть много, много других путей.
————————————
Первый случай:
Второй случай:
Идея нарисована так:
F(1) = 1;
F(2) = 2;
F(n) = F(n-1)+F(n-2) (n>=3)
Метод 1: рекурсивное решение
Поскольку код относительно прост, я не буду объяснять это слишком много здесь.
Как показано на рисунке, один и тот же цвет означает, что методу передается один и тот же параметр.
Метод 2: Меморандумный алгоритм
В приведенном выше коде карта коллекции представляет собой памятку. Каждый раз, когда необходимо вычислить F(N), он сначала находит соответствующий элемент на карте. Если он существует на карте, он возвращает результат напрямую.Если он не существует на карте, он вычисляет результат и сохраняет его в памятке.
Метод 3: Решатель динамического программирования
Программа повторяется, начиная с i=3 и заканчивая i=n. Для каждой итерации подсчитывается количество ходов на один шаг дальше. Во время итерации необходимо сохранить только две временные переменные a и b, которые представляют результаты предыдущей и предыдущей итераций соответственно. Для простоты понимания я ввел переменную temp. temp представляет значение результата текущей итерации.
Тема 2: Король и золотой рудник
В одной стране было обнаружено 5 золотых приисков.Каждый золотой прииск имеет разные запасы золота и разное количество рабочих, которые должны участвовать в добыче. Общее количество участвующих горняков – 10 человек. Каждый золотой рудник либо полностью добыт, либо не добыт, и половину людей нельзя отправить на добычу половины золота. Попросите программу решить, чтобы получить как можно больше золота, какие золотые прииски вы должны выбрать для добычи?
Способ 1: упорядочить и объединить
У каждого золотого рудника есть два варианта: добывать или не добывать.Если есть N золотых приисков, то есть 2^N вариантов в комбинации. Пройдите все возможности, исключите те варианты, которые используют более 10 рабочих, и среди оставшихся вариантов найдите вариант с наибольшим количеством золотых монет.
Код относительно прост и не будет показан, также очевидна временная сложность, которая составляет O(2^N).
F(n,w) = 0 (n<=1, w<p[0]);
F(n,w) = g[0] (n==1, w>=p[0]);
F(n,w) = F(n-1,w) (n>1, w<p[n-1])
F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n>1, w>=p[n-1])
Третья статья дополнена, и причину понять нетрудно.
Способ 2: простая рекурсия
Переведите уравнение перехода состояния в рекурсивную программу, а условием окончания рекурсии будет граница в уравнении. Поскольку каждое состояние имеет две оптимальные подструктуры, рекурсивный поток выполнения подобен бинарному дереву высоты N.
Временная сложность метода составляет O(2^N).
Метод 3: Меморандумный алгоритм
На основе простой рекурсии добавлен меморандум HashMap для хранения промежуточных результатов. Ключ HashMap — это объект, содержащий количество золотых приисков N и количество рабочих W, а Value — это количество золота, полученное при оптимальном выборе.
Временная сложность и пространственная сложность метода одинаковы и равны количеству различных ключей в памятке.
Способ 4: динамическое программирование
Метод использует два уровня итераций для постепенного получения конечного результата. В каждой итерации внешнего слоя, то есть в процессе итерации каждой строки таблицы, массив результатов preResults предыдущей строки будет сохраняться, а массив результатов results текущей строки будет вычисляться циклически.
Временная сложность метода составляет O(n * w), а пространственная сложность — (w). Следует отметить, что при наличии всего 5 золотых приисков преимущества динамического программирования в производительности не проявляются. При наличии 10 и более золотых приисков динамическое программирование имеет явное преимущество.
----- КОНЕЦ -----
Друзья, которым понравилась эта статья, нажмите и удерживайте изображение, чтобы следить за номером подписки.мечтать, смотрите больше захватывающего контента