Динамическое программирование java примеры

Solving the Fibonacci problem using Dynamic Programming in Java

Today, I am going to give a tutorial on how to solve the Fibonacci problem using Dynamic Programming in Java. Before we start to talk about Dynamic Programming. I would like to start briefly on what the Fibonacci problem is. If you already know the problem. Feel free to skip to the next section.

Fibonacci problem

According to Wikipedia, “Fibonacci number are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones”

For example: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

In modern usage, the sequence is extended by one more initial item: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

In any given sequence of Fn, it often represent as,
Fn = Fn-1 + Fn-2, with seed value of F1=1, F2=1 or F0=0, F1=1 depends on your first initial value.

These are the values at the nth of the Fibonacci sequence.

0	1	2	3	4	5	6	7	8	9	10
0	1	1	2	3	5	8	13	21	34	55

For example, at the 8th of Fibonacci sequence is 21.

Okay, now that we have Fibonacci problem covered. Let’s talk about Dynamic Programming and how it can be useful to us to solve this problem.

Dynamic Programming

The basic idea of Dynamic Programming is to save the result of the subproblem so that if we see it again in the future. We can simply use it instead of recomputing the value again. In the long run, it should save some or a lot of time which reduces the running time complexity of the problem. (which is what you should always try to do when doing competitive programming questions)

Let’s take the simple example of the Fibonacci numbers: finding the nth Fibonacci number defined by Fn = Fn-1 + Fn-2 and F0=0, F1=1

The easiest and obvious way of doing this is to use the recursion:

Recursion

By using the caching technique or Memoization, we have eliminate the needed to recomputed a lot of numbers as you can see in the tree diagram above. Hence, the running time should be improved tons. However, the space complexity of the problem just got increased to O(N) as we created a HashMap to store the results of the value. (acting as cache) However, this is still not perfect. As you can see, number 7 has been asked 1 time. Number 6 has been asked 2 times. Number 5 has been asked 2 times. Number 4 has been asked 2 times. Rest of the number got asked twice except 0. The next question is, is it possible that all the number will get computed/asked once and we get what we want at the end?

Yes, it is totally possible. Let’s try it.

Bottom Up

A better way to do this is to get rid of the recursion all-together by evaluating the results in the right order. Instead of top down, we are going for bottom up.

 public HashMapInteger, Integer> hm = new HashMapInteger, Integer>(); public int getFibonacciNumberBottomUpWithCache(int n)  hm.put(0, 0); hm.put(1, 1); for(int i = 2; i  n; i++)  hm.put(i, hm.get(i - 1) + hm.get(i - 2)); > return hm.get(n); >

Now that we are going with the right direction. Each number in the sequence ONLY gets touch once. Hence, the running time should get further improved here compared with the top down approach. However, the next question is, do we really need to save the results to the cache? and waste another O(N) space. The answer here is not really. We can use constant space and store the only necessary partial results along the way:

 public int getFibonacciNumberBottomUpWithoutCache(int n)  if (n == 0 || n == 1) return n; int fnMin2 = 0; int fnMin1 = 1; int sum = 0; for(int i = 2; i  n; i++)  sum = fnMin1 + fnMin2; fnMin2 = fnMin1; fnMin1 = sum; > return sum; >

Here, the runnning time for this approach should stay O(N) like above using the cache. However, we greatly reduced the space complexity from O(N) to O(1) constant space. Both running time and space complexity optimized.

Tada. You have done it using the Dynamic Programming way=)

Wrapping Up

This tutorial is largely based on a StackOverflow post by Tristan.

His idea of applying the Dynamic Programming is as follows:

• Find the recursion in the problem.
• Top-down: store the answer for each subproblem in a table to avoid having to recompute them.
• Bottom-up: Find the right order to evaluate the results so that partial results are available when needed.

Notes from his as well: Dynamic programming generally works for problems that have an inherent left to right order such as strings, trees or integer sequences. If the naive recursive algorithm does not compute the same subproblem multiple time, dynamic programming won’t help.

In case you want to run the live example, click the link here.

Hopefully this guide has help you to solve the Fibonacci problem using the Dynamic Programming. Thank you for reading!

Resources

I’ll try to keep this list current and up to date. If you know of a great resource you’d like to share or notice a broken link, please let us know.

Getting started

Share

PoAn (Baron) Chen

Software Engineer at Microsoft. Graduated from @uvic. Previously worked at @illumina, @ACDSee, @AEHelp and @AcePersonnel1. My words are my own.

Comments

Disclaimer: the theme of the site is largely based on will-jekyll-template by Willian Justen

Источник

Введение в динамическое программирование

Динамическое программирование — это метод решения сложной проблемы путем разбиения ее на набор более простых подзадач, решения каждой из этих подзадач только один раз и сохранения их решений с использованием структуры данных на основе памяти (массива, карты и т. д.). Каждое решение подзадачи каким-то образом индексируется, обычно на основе значений его входных параметров, чтобы облегчить его поиск. Таким образом, в следующий раз, когда возникает та же подзадача, вместо повторного вычисления ее решения выполняется поиск ранее вычисленного решения, тем самым экономя время вычислений. Этот метод хранения решений подзадач вместо их пересчета называется мемоизацией.

*writes down «1+1+1+1+1+1+1+1 What’s that equal to?»
*counting* «Eight!»
*writes down another «1+» on the left*
«What about that?»
*quickly* «Nine!»
«How’d you know it was nine so fast?»
«You just added one more.»
«So you didn’t need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say ‘remembering stuff to save time later'»

Есть два ключевых атрибута, которыми должна обладать проблема, чтобы динамическое программирование было применимо: оптимальное основание а также перекрывающиеся подзадачи.

1. Оптимальная подструктура

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

Например, кратчайший путь p из вершины u к вершине v в данном graph демонстрирует оптимальную подструктуру: возьмем любую промежуточную вершину w на этом кратчайшем пути p . Если p действительно кратчайший путь, то его можно разбить на подпути p₁ из u к w а также p₂ из w к v так что они, в свою очередь, действительно являются кратчайшими путями между соответствующими вершинами.

2. Перекрывающиеся подзадачи

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

Например, проблема вычисления последовательности Фибоначчи демонстрирует перекрывающиеся подзадачи. Проблема вычисления n’th число Фибоначчи F(n) можно разбить на подзадачи вычисления F(n-1) а также F(n-2) , а затем добавить два. Подзадача вычислений F(n-1) сама может быть разбита на подзадачу, которая включает в себя вычисление F(n-2) . Следовательно, вычисление F(n-2) используется повторно, и поэтому последовательность Фибоначчи демонстрирует перекрывающиеся подзадачи. Динамическое программирование учитывает этот факт и решает каждую подзадачу только один раз. Это может быть достигнуто любым из двух способов:

1. Подход «сверху вниз» (запоминание): Это прямое следствие рекурсивной формулировки любой проблемы. Если решение какой-либо задачи можно сформулировать рекурсивно, используя решение ее подзадач, и если ее подзадачи перекрываются, можно легко запомнить или сохранить решения подзадач в таблице. Всякий раз, когда мы пытаемся решить новую подзадачу, сначала проверяем таблицу, чтобы убедиться, что она уже решена. Если подзадача уже решена, используйте ее решение напрямую; в противном случае решите подзадачу и добавьте ее решение в таблицу.
2. Восходящий подход (таблица): Как только мы рекурсивно сформулируем решение проблемы в терминах ее подзадач, мы можем попробовать переформулировать проблему восходящим образом: сначала попытаться решить подзадачи, а затем использовать их решения для наращивания и получения решений более крупных подзадач. Это также обычно делается в табличной форме путем итеративного создания решений все более и более крупных подзадач с использованием решений небольших подзадач. Например, если мы уже знаем значения F(i-1) а также F(i-2) , мы можем непосредственно вычислить значение F(i) .

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

Рассмотрим наивную реализацию функции, находящей n’th член последовательности Фибоначчи:

Источник

Алгоритм Java: динамическое программирование

Метод деления состоит в том, чтобы просто разделить проблему на несколько подпрограмм. Когда проблема не независима, ситуация сложна.

Пример 1: номер ECHI Fibona

static int f(int i) < if(i < 1)< return 0; >if(i == 1) < return 1; >return f(i - 1) + f(i - 2); >

Хотя эта программа прекрасна, она недоступна, потому что требуется время, чтобы потратить индекс для расчета FN. Время расчета Fn+1 примерно в 1,6 раза больше, чем в Fn. Напротив, легко рассчитать FN в линейное время: вычислить предыдущий столбец глины N Fipona и поместить их в массив:

Количество столбцов увеличилось, поэтому массив не большой.

Эта технология предоставляет нам прямой метод получения численного решения для получения любых рекурсивных отношений.

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

Пример 2: фибонин aquiter (динамическое программирование)

1. static final int maxN= 47 ;
2. static int knownF[]= new int [maxN];
3. static int f( int i)
4. if (knownF[i]!= 0 )
5. return knownF[i];
6. >
7. int t=i;
8. if (i < 0 )
9. return 0 ;
10. >
11. if (i> 1 )
12. t=f(i- 1 )+f(i- 2 );
13. >
14. return knownf[i]=t;
15. >

static final int maxN = 47; static int knownF [] = new int [maxN]; static int f(int i) < if(knownF[i] != 0)< return knownF[i]; >int t = i; if(i < 0)< return 0; >if(i > 1) < t = f(i - 1) + f(i - 2); >return knownf[i] = t; >

Хранив рассчитанное значение в статическом массиве, любые дублируемые расчеты четко избегаются.

Пример 3: Проблемы с рюкзаком (рекурсивная реализация)

Предположим, существует множество n пункта товара ::

static int knap(int cap)< int i, space, max, t; for(i = 0, max = 0; i < N; i++)< if((space = cap - items[i].size) >= 0) < if((t = knap(space) + items[i].val) >max) < max = t; >> > return max; >

Пример 4: Задача рюкзака (динамическое программирование)

1. static int knap( int m)
2. int i,space,max,maxi= 0 ,t;
3. if (maxKnown[m]!=unknown)
4. return maxKnown[m];
5. >
6. for (i= 0 ,max= 0 ;i if ((space=m-items[i].size)>= 0 )
7. if ((t=knap(space)+items[i].val)>max)
8. max=t;
9. maxi=i;
10. >
11. >
12. >
13. maxKnown[m]=max;
14. itemKnown[m]=items[maxi];
15. return max;
16. >

static int knap(int m) < int i, space, max, maxi = 0, t; if(maxKnown[m] != unknown)< return maxKnown[m]; >for(i = 0, max = 0; i < N; i++)< if((space = m - items[i].size) >= 0) < if((t = knap(space) + items[i].val) >max) < max = t; maxi = i; >> > maxKnown[m] = max; itemKnown[m] = items[maxi]; return max; >

Время выполнения рюкзака пропорционально MN. Когда пропускная способность не большая, проблема может быть легко решена; требования времени и пространства для рюкзаков с большой каплей могут быть слишком большими.

Динамическое программирование снизу также применимо к проблеме рюкзака.

В динамическом программировании снизу вычислите его заранее. Обычно, более предпочтительнее использовать динамическое программирование сверху вместо дна, потому что: это механическое преобразование раствора естественного решения в план задачи. Динамическое программирование сверху является основным методом эффективного реализации рекурсивного алгоритма, и это важный инструмент для тех, кто занимается проектированием и реализацией алгоритмов.

Источник