What is dynamic programming? [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 2 years ago.

Improve this question

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.

Answer 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.

Answer 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

Answer 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.

Answer 4

It's an optimization of your algorithm that cuts running time.

While a Greedy Algorithm is usually called naive, because it may run multiple times over the same set of data, Dynamic Programming avoids this pitfall through a deeper understanding of the partial results that must be stored to help build the final solution.

A simple example is traversing a tree or a graph only through the nodes that would contribute with the solution, or putting into a table the solutions that you've found so far so you can avoid traversing the same nodes over and over.

Here's an example of a problem that's suited for dynamic programming, from UVA's online judge: Edit Steps Ladder.

I'm going to make quick briefing of the important part of this problem's analysis, taken from the book Programming Challenges, I suggest you check it out.

Take a good look at that problem, if we define a cost function telling us how far appart two strings are, we have two consider the three natural types of changes:

Substitution - change a single character from pattern "s" to a different character in text "t", such as changing "shot" to "spot".

Insertion - insert a single character into pattern "s" to help it match text "t", such as changing "ago" to "agog".

Deletion - delete a single character from pattern "s" to help it match text "t", such as changing "hour" to "our".

When we set each of this operations to cost one step we define the edit distance between two strings. So how do we compute it?

We can define a recursive algorithm using the observation that the last character in the string must be either matched, substituted, inserted or deleted. Chopping off the characters in the last edit operation leaves a pair operation leaves a pair of smaller strings. Let i and j be the last character of the relevant prefix of and t, respectively. there are three pairs of shorter strings after the last operation, corresponding to the string after a match/substitution, insertion or deletion. If we knew the cost of editing the three pairs of smaller strings, we could decide which option leads to the best solution and choose that option accordingly. We can learn this cost, through the awesome thing that's recursion:

#define MATCH 0 /* enumerated type symbol for match */
#define INSERT 1 /* enumerated type symbol for insert */
#define DELETE 2 /* enumerated type symbol for delete */


int string_compare(char *s, char *t, int i, int j)

{

    int k; /* counter */
    int opt[3]; /* cost of the three options */
    int lowest_cost; /* lowest cost */
    if (i == 0) return(j * indel(’ ’));
    if (j == 0) return(i * indel(’ ’));
    opt[MATCH] = string_compare(s,t,i-1,j-1) +
      match(s[i],t[j]);
    opt[INSERT] = string_compare(s,t,i,j-1) +
      indel(t[j]);
    opt[DELETE] = string_compare(s,t,i-1,j) +
      indel(s[i]);
    lowest_cost = opt[MATCH];
    for (k=INSERT; k<=DELETE; k++)
    if (opt[k] < lowest_cost) lowest_cost = opt[k];
    return( lowest_cost );

}

This algorithm is correct, but is also impossibly slow.

Running on our computer, it takes several seconds to compare two 11-character strings, and the computation disappears into never-never land on anything longer.

Why is the algorithm so slow? It takes exponential time because it recomputes values again and again and again. At every position in the string, the recursion branches three ways, meaning it grows at a rate of at least 3^n – indeed, even faster since most of the calls reduce only one of the two indices, not both of them.

So how can we make the algorithm practical? The important observation is that most of these recursive calls are computing things that have already been computed before. How do we know? Well, there can only be |s| · |t| possible unique recursive calls, since there are only that many distinct (i, j) pairs to serve as the parameters of recursive calls.

By storing the values for each of these (i, j) pairs in a table, we can avoid recomputing them and just look them up as needed.

The table is a two-dimensional matrix m where each of the |s|·|t| cells contains the cost of the optimal solution of this subproblem, as well as a parent pointer explaining how we got to this location:

typedef struct {
int cost; /* cost of reaching this cell */
int parent; /* parent cell */
} cell;

cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */

The dynamic programming version has three differences from the recursive version.

First, it gets its intermediate values using table lookup instead of recursive calls.

**Second,**it updates the parent field of each cell, which will enable us to reconstruct the edit sequence later.

**Third,**Third, it is instrumented using a more general goal cell() function instead of just returning m[|s|][|t|].cost. This will enable us to apply this routine to a wider class of problems.

Here, a very particular analysis of what it takes to gather the most optimal partial results, is what makes the solution a "dynamic" one.

Here's an alternate, full solution to the same problem. It's also a "dynamic" one even though its execution is different. I suggest you check out how efficient the solution is by submitting it to UVA's online judge. I find amazing how such a heavy problem was tackled so efficiently.

Answer 5

The key bits of dynamic programming are "overlapping sub-problems" and "optimal substructure". These properties of a problem mean that an optimal solution is composed of the optimal solutions to its sub-problems. For instance, shortest path problems exhibit optimal substructure. The shortest path from A to C is the shortest path from A to some node B followed by the shortest path from that node B to C.

In greater detail, to solve a shortest-path problem you will:

• find the distances from the starting node to every node touching it (say from A to B and C)
• find the distances from those nodes to the nodes touching them (from B to D and E, and from C to E and F)
• we now know the shortest path from A to E: it is the shortest sum of A-x and x-E for some node x that we have visited (either B or C)
• repeat this process until we reach the final destination node

Because we are working bottom-up, we already have solutions to the sub-problems when it comes time to use them, by memoizing them.

Remember, dynamic programming problems must have both overlapping sub-problems, and optimal substructure. Generating the Fibonacci sequence is not a dynamic programming problem; it utilizes memoization because it has overlapping sub-problems, but it does not have optimal substructure (because there is no optimization problem involved).

Answer 6

Dynamic Programming

Definition

Dynamic programming (DP) is a general algorithm design technique for solving problems with overlapping sub-problems. This technique was invented by American mathematician “Richard Bellman” in 1950s.

Key Idea

The key idea is to save answers of overlapping smaller sub-problems to avoid recomputation.

Dynamic Programming Properties

• An instance is solved using the solutions for smaller instances.
• The solutions for a smaller instance might be needed multiple times, so store their results in a table.
• Thus each smaller instance is solved only once.
• Additional space is used to save time.

Answer 7

I am also very much new to Dynamic Programming (a powerful algorithm for particular type of problems)

In most simple words, just think dynamic programming as a recursive approach with using the previous knowledge

Previous knowledge is what matters here the most, Keep track of the solution of the sub-problems you already have.

Consider this, most basic example for dp from Wikipedia

Finding the fibonacci sequence

function fib(n)   // naive implementation
    if n <=1 return n
    return fib(n − 1) + fib(n − 2)

Lets break down the function call with say n = 5

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(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

In particular, fib(2) was calculated three times from scratch. In larger examples, many more values of fib, or sub-problems, are recalculated, leading to an exponential time algorithm.

Now, lets try it by storing the value we already found out in a data-structure say a Map

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

Here we are saving the solution of sub-problems in the map, if we don't have it already. This technique of saving values which we already had calculated is termed as Memoization.

At last, For a problem, first try to find the states (possible sub-problems and try to think of the better recursion approach so that you can use the solution of previous sub-problem into further ones).

Answer 8

Dynamic programming is a technique for solving problems with overlapping sub problems. A dynamic programming algorithm solves every sub problem just once and then Saves its answer in a table (array). Avoiding the work of re-computing the answer every time the sub problem is encountered. The underlying idea of dynamic programming is: Avoid calculating the same stuff twice, usually by keeping a table of known results of sub problems.

The seven steps in the development of a dynamic programming algorithm are as follows:

1. Establish a recursive property that gives the solution to an instance of the problem.
2. Develop a recursive algorithm as per recursive property
3. See if same instance of the problem is being solved again an again in recursive calls
4. Develop a memoized recursive algorithm
5. See the pattern in storing the data in the memory
6. Convert the memoized recursive algorithm into iterative algorithm
7. Optimize the iterative algorithm by using the storage as required (storage optimization)

Answer 9

in short the difference between recursion memoization and Dynamic programming

Dynamic programming as name suggest is using the previous calculated value to dynamically construct the next new solution

Where to apply dynamic programming : If you solution is based on optimal substructure and overlapping sub problem then in that case using the earlier calculated value will be useful so you do not have to recompute it. It is bottom up approach. Suppose you need to calculate fib(n) in that case all you need to do is add the previous calculated value of fib(n-1) and fib(n-2)

Recursion : Basically subdividing you problem into smaller part to solve it with ease but keep it in mind it does not avoid re computation if we have same value calculated previously in other recursion call.

Memoization : Basically storing the old calculated recursion value in table is known as memoization which will avoid re-computation if its already been calculated by some previous call so any value will be calculated once. So before calculating we check whether this value has already been calculated or not if already calculated then we return the same from table instead of recomputing. It is also top down approach

Answer 10

Here is a simple python code example of Recursive, Top-down, Bottom-up approach for Fibonacci series:

Recursive: O(2ⁿ)

def fib_recursive(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)


print(fib_recursive(40))

Top-down: O(n) Efficient for larger input

def fib_memoize_or_top_down(n, mem):
    if mem[n] is not 0:
        return mem[n]
    else:
        mem[n] = fib_memoize_or_top_down(n-1, mem) + fib_memoize_or_top_down(n-2, mem)
        return mem[n]


n = 40
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
print(fib_memoize_or_top_down(n, mem))

Bottom-up: O(n) For simplicity and small input sizes

def fib_bottom_up(n):
    mem = [0] * (n+1)
    mem[1] = 1
    mem[2] = 1
    if n == 1 or n == 2:
        return 1

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

    return mem[n]


print(fib_bottom_up(40))