What is dynamic programming? [closed]

What is dynamic programming?

How is it different from recursion, memoization, etc?

I have read the wikipedia article on it, but I still don't really understand it.

Solution 1:

Dynamic programming is when you use past knowledge to make solving a future problem easier.

A good example is solving the Fibonacci sequence for n=1,000,002.

This will be a very long process, but what if I give you the results for n=1,000,000 and n=1,000,001? Suddenly the problem just became more manageable.

Dynamic programming is used a lot in string problems, such as the string edit problem. You solve a subset(s) of the problem and then use that information to solve the more difficult original problem.

With dynamic programming, you store your results in some sort of table generally. When you need the answer to a problem, you reference the table and see if you already know what it is. If not, you use the data in your table to give yourself a stepping stone towards the answer.

The Cormen Algorithms book has a great chapter about dynamic programming. AND it's free on Google Books! Check it out here.

Solution 2:

Dynamic programming is a technique used to avoid computing multiple times the same subproblem in a recursive algorithm.

Let's take the simple example of the Fibonacci numbers: finding the n ^th Fibonacci number defined by

F_n = F_n-1 + F_n-2 and F₀ = 0, F₁ = 1

Recursion

The obvious way to do this is recursive:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

Dynamic Programming

• Top Down - Memoization

The recursion does a lot of unnecessary calculations because a given Fibonacci number will be calculated multiple times. An easy way to improve this is to cache the results:

cache = {}

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n in cache:
        return cache[n]

    cache[n] = fibonacci(n - 1) + fibonacci(n - 2)

    return cache[n]

• 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:

cache = {}

def fibonacci(n):
    cache[0] = 0
    cache[1] = 1

    for i in range(2, n + 1):
        cache[i] = cache[i - 1] +  cache[i - 2]

    return cache[n]

We can even use constant space and store only the necessary partial results along the way:

def fibonacci(n):
  fi_minus_2 = 0
  fi_minus_1 = 1

  for i in range(2, n + 1):
      fi = fi_minus_1 + fi_minus_2
      fi_minus_1, fi_minus_2 = fi, fi_minus_1

  return fi

• How apply dynamic programming?

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

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 times, dynamic programming won't help.

I made a collection of problems to help understand the logic: https://github.com/tristanguigue/dynamic-programing

Solution 3:

Memoization is the when you store previous results of a function call (a real function always returns the same thing, given the same inputs). It doesn't make a difference for algorithmic complexity before the results are stored.

Recursion is the method of a function calling itself, usually with a smaller dataset. Since most recursive functions can be converted to similar iterative functions, this doesn't make a difference for algorithmic complexity either.

Dynamic programming is the process of solving easier-to-solve sub-problems and building up the answer from that. Most DP algorithms will be in the running times between a Greedy algorithm (if one exists) and an exponential (enumerate all possibilities and find the best one) algorithm.

• DP algorithms could be implemented with recursion, but they don't have to be.
• DP algorithms can't be sped up by memoization, since each sub-problem is only ever solved (or the "solve" function called) once.