What is dynamic programming

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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    Establish a recursive property that gives the solution to an instance of the problem  Develop a recursive algorithm as per recursive property See if same instance of the problem is being solved again an again in recursive calls Develop a memoized recursive algorithm See the pattern in storing the data in the memory  Convert the memoized recursive algorithm into iterative algorithm Optimize the iterative algorithm by using the storage as required  storage optimization

User · Answer

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

User · Answer

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 lt  DELETE  k        if  opt k   lt  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

User · Answer

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  lt  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

User · Answer

Here is a simple python code example of Recursive  Top-down  Bottom-up approach for Fibonacci series   Recursive  O 2n     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

User · Answer

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

User · Answer

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

[algorithm] What is dynamic programming?

Recursion

Dynamic Programming

Examples related to algorithm

Examples related to dynamic-programming