Ctrl+K

Dynamic Programming

Dynamic Programming#

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.

FAn optimization problem can be solved using dynamic programming if the problem has the following properties:

  1. Overlapping Subproblems

  2. Optimal Substructure

Overlapping Subproblems#

Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems. Dynamic Programming is mainly used when solutions of same subproblems are needed again and again. In dynamic programming, computed solutions to subproblems are stored in a table so that these don’t have to be recomputed. So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point storing the solutions if they are not needed again.

Example

Recursive program for Fibonacci Numbers, there are many subproblems which are solved again and again.

                          fib(5)
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

Optimal Substructure#

A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.

Example

The Shortest Path problem has following optimal substructure property:

If a node x lies in the shortest path from a source node u to destination node v then 
shortest path from u to v is combination of shortest path from u to x and shortest path from x to v.

The standard All Pair Shortest Path algorithms like Floyd–Warshall and Bellman–Ford are typical examples of Dynamic Programming.

Tabulation vs Memoization#

There are following two different ways to store the values so that the values of a sub-problem can be reused. Here, will discuss two patterns of solving DP problem:

  1. Tabulation (Bottom Up)

  2. Memoization (Top Down)

Tabulation Method (Bottom Up Dynamic Programming)#

As the name itself suggests starting from the bottom and cumulating answers to the top. Let’s discuss in terms of state transition.

Let’s describe a state for our DP problem to be dp[x] with dp[0] as base state and dp[n] as our destination state. So, we need to find the value of destination state i.e dp[n].

If we start our transition from our base state i.e dp[0] and follow our state transition relation to reach our destination state dp[n], we call it Bottom Up approach as it is quite clear that we started our transition from the bottom base state and reached the top most desired state.

Memoization Method (Top Down Dynamic Programming)#

Let’s describe it in terms of state transition. If we need to find the value for some state say dp[n] and instead of starting from the base state that i.e dp[0] we ask our answer from the states that can reach the destination state dp[n] following the state transition relation, then it is the top-down fashion of DP.

Here, we start our journey from the top most destination state and compute its answer by taking in count the values of states that can reach the destination state, till we reach the bottom most base state.

Tabulation (Bottom Up)

Memoization (Top Down )

State

State transition relation is difficult to think

State transition relation is easy to think

Code

Code is complicated with a lot conditions

Code is easy and less complicated

Speed

Fast

Slow

Sub-Problem Solving

All sub-problems are solved

Solves only required sub-problems

Table Entries

All entries are filled.

Entries are filled on demand

 
fibonacci_table = [0, 1]
def fibonacci_tabulation(n):

    for i in range(2, n + 1):
        fib_num = fibonacci_table[i - 1] + fibonacci_table[i - 2]
        fibonacci_table.append(fib_num)
    
    return fibonacci_table[-1]

fibonacci_lookups = {}
def fibonacci_memoization(n):

    if n in fibonacci_lookups:
        return fibonacci_lookups[n]

    if n < 2:  # base case
        fibonacci_lookups[n] = n
        return fibonacci_lookups[n]

    fibonacci_lookups[n] = fibonacci_memoization(n - 1) + fibonacci_memoization(n - 2)

    return fibonacci_lookups[n]

n = 500
print(fibonacci_tabulation(n))
print(fibonacci_memoization(n))

139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
Contents