Dynamic programming is a computer programming method used to avoid computing multiple time the same subproblem in a recursive algorithm.

Dynamic programming is applied to optimization problems where can be many possible solutions. Each solution has a value what can be found by solution with the optimal (minimum or maximum) value. This solution calls an optimal solution to the problem.

Dynamic programming method can design in 4 steps:

1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution in a bottom-up fashion.
4. Construct an optimal solution from computed information.

*Some of the algorithm problems can be solved by the "divide and conquer" strategy instead of Dynamic programming. For example:

• Merge sort
• Quick sort

Solutions for these algorithms not overlapping sub-problems, so they not classified as dynamic programming problems.

Numbers( 0,1,1,2,3,5,8,13,21,34...), it’s the Fibonacci sequence, described by the recursive formula:

F(0) = 0, (1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.

Fibonacci sequence which approximates the golden spiral.

The spiral is drawn starting from the inner 1×1 square and continues outwards to successively larger squares.

Vizualization Fibonacci sequence

Commonly denoted F(n) form a sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

Given N, calculate F(N). Fibonacci sequence most common example to Dynamic programming method.

Trivial algorithm for computing F(N):

if n = 0: return 0
else if n = 1: return 1
else: return naive F(n − 1) + F(n − 2)

JavaScript implementation:

/**
 * Time complexity: O(2^n)
 * Space complexity: O(n)
 *
 * @param number N
 * @return number
 */
function getFibonacciNumberRecursive(N) {
  if (N <= 2) {
    return N < 1 ? 0 : 1;
  }
  return getFibonacciNumberRecursive(N - 1) + getFibonacciNumberRecursive(N - 2);
}

To calculate F(n) as sum of time to calculate F(n-1) and F(n-2), plus time to calculate them together O(1):

T(n<=1) = O(1) - for all operations F(1), F(0)

T(n) = T(n − 1) + T(n − 2) + O(1)
T(n) = T(n − 1) + T(n − 2) + c
2^kT(n − 2 * k) + c(2^(k−1) + 2^(k−2) + . . . + 2 + 1) = Ω(c2 ^ (n/2))

Where "c" is the time needed to add n-bit numbers. Since

T(n) = Ω(n2 ^ n/2) => T(n) = O(2^n)

O(2^n) - exponential time and O(n) space complexity for call stack size.

To describe O(2^n) time complexity, let's draw the recursion tree of calls, which will have depth n and intuitively figure out that this function is asymptotically O(2^n).

To prove this conjecture by induction, let shows recursion tree for F(5)

                                        /<------------- F(5) ------------------>\
                                      /                                          \
                                F(4)[F(n - 1)]                                    F(3)[F(n - 2)]
                               /               \                                  /             \
                              /                 \                                /               \
                     F(3)[F(n - 1)]              F(2)[F(n - 2)]                 F(2)[F(n - 1)]    F(1)[F(n - 2)]
                     /           \               /             \                /             \
                    /             \             /               \              /               \
      F(2)[F(n - 1)]             F(2)[F(n - 1)] F(1)[F(n - 1)] F(0)[F(n - 2)]  F(1)[F(n - 1)]  F(0)[F(n - 2)]
      /             \
     /               \
  F(1)[F(n - 1)]      F(0)[F(n - 2)]

In provide recursion tree of calls example, getFibonacciNumberRecursive(5) or F(5) function make multiple executions with same arguments:

• F(2) - 4 times
• F(3) - 2 times
• The leaves of the recursion tree will always return 1 (F(1) and F(0))

Assume T(n-1) = O(2^(n-1)), therefore

T(n) = T(n-1) + T(n-2) + O(1) which is equal to
T(n) = O(2 ^ (n-1)) + O(2 ^ (n-2)) + O(1) = O(2^n)

Consequently, the tight bound for this function is the Fibonacci sequence itself (~θ(1.6^n)) which related to Golden ratio

Vizualization Golden ratio with numbers

Simple way to optimeze function getFibonacciNumberRecursive, create a chache Object for memoize storage. Runtime, assuming n-bit registers for each entry of memo data structure(cache Object):

T(n) = T(n − 1) + O(1) = O(n)
T(n) = T(n − 1) + c = O(cn)
T(n) = O(n ^ 2)

• Show updated recursion tree for F(5) with Memoization method below.

                                        /<------------- F(5) ------------------>\
                                      /                                          \
                                F(4)[F(n - 1)]                                    memo[F(3)]
                               /               \ 
                              /                 \ 
                     F(3)[F(n - 1)]              memo[F(2)]
                     /           \
                    /             \
       F(2)[F(n - 1)]              memo[F(2)]
      /             \
     /               \
  F(1)[F(n - 1)]      F(0)[F(n - 2)]
  

JavaScript implementation:

/*
 * @param memo - cache storage object
 */
const memo = {};

/**
 * Time complexity: O(n ^ 2)
 * Space complexity: O(n)
 *
 * @param number N
 * @return number
 */
function getFibonacciNumberRecursive(N) {
  if (N <= 2) {
    return N < 1 ? 0 : 1;
  }
  if (!memo[N]) {
    memo[N] = getFibonacciNumberRecursive(N - 1) + getFibonacciNumberRecursive(N - 2);
  }
  return memo[N];
}

In recursion tree of calls example, (5) or F(5) function make one execution with same arguments:

• F(2) - 1 times
• F(3) - 1 times

Alternative optimization recursion version, can be implementation of tail recursion. Calculate the results first, and pass the results of your current call onto the next recursive call.

Tail recursion JavaScript implementation.

/**
 * Time complexity: O(n)
 * Space complexity: O(n)
 *
 * @param number N
 * @return number
 */
function getFibonacciNumberTailRecursion (n, a = 0, b = 1){
  if (n > 0) {
    return getFibonacciNumberTailRecursion(n - 1, b, a + b);
  }
  return a;
}

In the tail-recursive case, with each evaluation of the recursive call, the running total is updated.

To prove this conjecture by induction, let shows calls for F(5) tail recursion method.

F(5 , 1, 1)
    ||
    \/
F(4 , 2, 1)
    ||
    \/
F(3 , 3, 2)
    ||
    \/
F(2 , 5, 3)

Result - 5

• This methodics result of Dynamic programming investigation from Tail Recursion.

Based on tail recursion implementation, for recrusion calls stack need O(n) space complexity. If modify implementation to iterative solution, solving Fibonacci sequence with O(1) space complexity, simply store the previous two numbers only. Because only two numbers need to get the next Fibonacci number in series. Single for loop operation take O(n) time complexity, for space complexity using 3 variables O(3) => O(1).

JavaScript iterative implementation

/**
 * Iterative
 * Time complexity: O(n)
 * Space complexity: O(1)
 *
 * @param number N
 * @return number
 */
function getFibonacciNumberIterative(N) {
  if (N <= 1) {
    return N;
  }
  let a = 0;
  let b = 1;
  let sum = null;

  for (let i = 2; i <= N; i++) {
    sum = a + b;
    a = b;
    b = sum;
  }

  return b;
}

Iterative calls in for loop operations for N = 5

i(2), a(0), b(1), sum(null) // on init
    ||
    \/
i(3), a(1), b(1), sum(1)
    ||
    \/
i(4), a(1), b(2), sum(2)
    ||
    \/
i(5), a(2), b(3), sum(3)

Result b = sum = a(2) + b(3) = 5

More faster Math solution can be implemented based on Math formula calculation. This solution just bonus reference and not related to Dynamic programming topic.

/**
 * Time complexity: O(1)
 * Space complexity: O(1)
 *
 * http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html
 * @param number N
 * @return number
 */
function getFibonacciNumberMath (N){
  return parsetInt(Math.round(Math.pow((1 + Math.sqrt(5)) / 2, N) / Math.sqrt(5))); 
}

Formula provide by this reference.