Dynamic Programming
Dynamic programming is an optimization technique that utilizes recursion and specific rules to address, for example, NP-hard problems. The concept involves storing solutions for subproblems and reusing them when necessary, rather than recalculating their values. This approach frequently transforms the runtime complexity from exponential to polynomial, enhancing computational efficiency.
Table of Contents
Rules of dynamic programming
When describing an algorithm it is defined as a dynamic algorithm if the following principles of optimization are suitable for it:
- Optimal substructure property
=>A problem can be broken down to subproblems and is solved only once
- Overlapping subproblems
=>The solution of a subproblem might help you finding a feaseable solution for the actual problem.
Branch and reduce framework
Example dynamic programs
A good example of dynamic solution is the algorithm for fibonnacci numbers. The usual known version is to find numbers by using this recursive version.
proc fib(n: int): int
if n∈{0,1} then
return 1
else
return fib(n-1)+fib(n-2)Using this algorithm the solution would be in exponential runtime such that finding big numbers will take a lot of time.
If whe change the algorithm to store already solved numbers instead of always doing it again we can archieve a linear runtime.
numbers = array of integer
proc fib(n: int): int
numbers[0] = 1
numbers[1] = 1
for i = 2 to n do
numbers[i] = numbers[i-1]+numbers[i-2]
return numbers[n]
This version will store 1 for the first two fib numbers and afterwards solve all following numbers using the previous stored numbers until the searched fibonnacci number is found.
The algorithm is in O(n) because working with arrays needs O(1) and we perform it n times. It fullfills both rules of dynamic programming and is a dynamic algorithm.
Sources
https://www.geeksforgeeks.org/dynamic-programming/ (26.1.2024 14:28)
https://en.wikipedia.org/wiki/Dynamic_programming (26.1.2024 14:32)