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.

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)