Я недавно попал в Динамическое программирование. Я начал свое путешествие сначала с просмотра нескольких видеороликов на YouTube, затем постепенно перешел к чтению контента и, наконец, к решению проблем.

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

t2 = t1 + t0;

Вы можете использовать два подхода к решению этой проблемы: итеративный или рекурсивный.

У многих возникают проблемы с рекурсивным решением этой задачи. Я тоже. Затем я провел несколько часов и дней, разбираясь с рекурсивными структурами и методами. Мне это еще не совсем понятно, но я начинаю, наконец, вникать в это.

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

t2 = t0 + t1^2;
// Here we are going to find the next value in the sequence by taking the sum of the previous' element's value squared and the value of the element two elements back

Метод повторения:

Идея здесь состоит в том, чтобы вычислить n-е значение Фибоначчи по первому и второму члену последовательности. В следующем решении я ожидаю, что очень большие числа будут частью решения, поэтому я немного потренируюсь с классом BigInteger, предоставленным из пространства имен System.Numerics.

Переменная val представляет n-е значение последовательности. Поскольку моя итерация основана на нуле, мне нужно вычесть единицу, чтобы не вычислять слишком много. Я дополнительно вычитаю еще один, потому что заранее вычисляю окончательный ответ. Расчет происходит до того, как я обновлю первое и второе.

Это решение может быть лучше, однако оно работает и соответствует нашим потребностям.

Рекурсия и динамическое программирование:

Этот код на самом деле намного проще читать, но его гораздо сложнее понять, по крайней мере, сначала. Во всех задачах динамического программирования вам нужно объявить базовые случаи, чтобы рекурсия остановилась, а для ваш стек рухнет.

Итак, в следующем решении я передаю свои базовые случаи каждой итерации метода. Никакой запоминаемостью я не пользуюсь, потому что совсем о ней забыл до сих пор.

Мне потребовалось гораздо больше времени, чтобы подумать (а также протестировать) это решение, хотя кажется, что здесь не так много кода.

Несмотря на то, что мы не используем здесь так много места для вычисления значений последовательности, мы имеем временную сложность O(2^n). Это довольно страшно, когда вы начинаете вычислять большие последовательности. Мемоизация помогает решить эту проблему и подзадачи.

Добро пожаловать в динамическое программирование!