What is dynamic programming?

Question

What is dynamic programming ?

Dynamic programming NAY is dynamic typing

• What are its characteristics ?
• What are its advantages and disadvantages ?

Answer 1

When you start working with more than one system, you can run a series of conflicts due to the use of recursive algorithms, which re-examine the same problem many times, and in this situation, generating new conflicts and bugs.

To solve these problems, there is the dynamic programming, that it is a methodology for constructing algorithms that solve original system problems in a way that optimises and makes use of combinatorial analysis, to prevent performance drop and unnecessary recalculations to meet subsystems that may surpass the original system, generating new subproblems.

That is, when you start programming, the ideal is for you to think about abstracting as much as you can so that there are no problems in the future, this is a dynamic thinking.

Answer 2

"Many efficient algorithms follow the dynamic programming paradigm. This paradigm, or algorithm design strategy, is a kind of intelligent iterative translation of recursion and can be loosely defined as recursion with table support.

As in a recursive algorithm, each instance of the problem is solved from the solution of smaller instances, or rather from sub-instances of the original instance. The distinctive feature of dynamic programming is the table that stores the solutions of the various sub-intervals. The time consumption of the algorithm is, in general, proportional to the table size."

Source: http://www.ime.usp.br/~pf/analy_de_algoritmos/classes/Dynamic-Programming.html

Answer 3

A known and simple problem that is commonly used to demonstrate dynamic programming is the recursive calculation of Fibonacci numbers.

In Moon this calculation is made so:

function fib(n)
  if n == 0 then
    return 1
  elseif n == 1 then
    return 1
  else
    return fib(n-1) + fib(n-2)
  end
end

for n = 1, 10 do
  io.write(fib(n), ", ")
end
io.write("...\n")

A version of this program showing recursive calls made:

local newline = false
local N = arg[1] or 5

function print_level(lev)
  if newline then
    io.write(string.rep(" ", 9*lev))
    newline = false
  end
end

function fib(n, level)

  if n == 0 then
    print_level(level)
    io.write(" --> f(0)\n")
    newline = true
    return 1

  elseif n == 1 then
    print_level(level)
    io.write(" --> f(1)\n")
    newline = true
    return 1

  else
    print_level(level)
    io.write(" --> f(" .. n .. ")")
    return fib(n-1, level+1) + fib(n-2, level+1)
  end
end

print "----------------------------"
print(" calculando fib(" .. N .. ")")
local f = fib(tonumber(N), 0)
print(" fib(" .. N .. ")=" .. f)
print "----------------------------"

Calculation of Fib(0) up to Fib(5)

$ lua fib.lua 0                                  
----------------------------                     
 calculando fib(0)                               
 --> f(0)                                        
 fib(0)=1                                        
----------------------------                     

$ lua fib.lua 1                                  
----------------------------                     
 calculando fib(1)                               
 --> f(1)                                        
 fib(1)=1                                        
----------------------------                     

$ lua fib.lua 2                                  
----------------------------                     
 calculando fib(2)                               
 --> f(2) --> f(1)                               
          --> f(0)                               
 fib(2)=2                                        
----------------------------                     

$ lua fib.lua 3                                  
----------------------------                     
 calculando fib(3)                               
 --> f(3) --> f(2) --> f(1)                      
                   --> f(0)                      
          --> f(1)                               
 fib(3)=3                                        
----------------------------                     

$ lua fib.lua 4                                  
----------------------------                     
 calculando fib(4)                               
 --> f(4) --> f(3) --> f(2) --> f(1)             
                            --> f(0)             
                   --> f(1)                      
          --> f(2) --> f(1)                      
                   --> f(0)                      
 fib(4)=5                                        
----------------------------                     

 $ lua fib.lua 5
 ----------------------------                         
 calculando fib(5)                                   
 --> f(5) --> f(4) --> f(3) --> f(2) --> f(1)        
                                     --> f(0)        
                            --> f(1)                 
                   --> f(2) --> f(1)                 
                            --> f(0)                 
          --> f(3) --> f(2) --> f(1)                 
                            --> f(0)                 
                   --> f(1)                          
 fib(5)=8                                            
----------------------------                         

What you see is a lot of repeated calculations. For Fib(10), for example, Fib(0) is calculated 34 times, and Fib(1) is calculated 55 times.

One way to avoid these repeated calculations is to store a value in memory (dictionary, hash, etc., depending on the language) that is calculated the first time. The other times just refer to the map in memory, and if the value has already been calculated then it does not need to be recalculated.

Program above using this calculation method:

local newline = false
local N = arg[1] or 5

local cache = {}

function print_level(lev)
  if newline then
    io.write(string.rep(" ", 9*lev))
    newline = false
  end
end

function fib(n, level)

  if n == 0 then
    print_level(level)
    io.write(" --> f(0)\n")
    newline = true
    return 1

  elseif n == 1 then
    print_level(level)
    io.write(" --> f(1)\n")
    newline = true
    return 1

  else
    print_level(level)
    io.write(" --> f(" .. n .. ")")
    local saved = cache[n]
    if saved then
      io.write("\n")
      newline = true
      return saved
    else
      saved = fib(n-1, level+1) + fib(n-2, level+1)
      cache[n] = saved
      return saved
    end
  end
end

print "----------------------------"
print(" calculando fib(" .. N .. ")")
local f = fib(tonumber(N), 0)
io.write("\n")
print(" fib(" .. N .. ")=" .. f)
print "----------------------------"

In this version, when calculating Fib(10), Fib(0) is calculated only once, and Fib(1) is calculated twice!

To check these numbers, use the following commands:

$ fib_v1(10) | grep -c "f(0)"
$ fib_v1(10) | grep -c "f(1)"

and

$ fib_v2(10) | grep -c "f(0)"
$ fib_v2(10) | grep -c "f(1)"

Answer 4

Dynamic programming is a paradigm applied to complex computation problems, a methodology of constructing algorithms that solve original system problems in a way that optimizes and makes use of combinatorial analysis, to prevent performance drop and unnecessary recalculations. We can associate to it resources as recursiveness of a code.

As for the advantages:

• Implementation ensures practicality when applied to code that requires testing with all possibilities.

• Numerical accuracy is not important.

DISADVANTAGES:

• Consumes a lot of memory for processing.

• Depending on the problem, the spatial complexity of the problem can become gigantic.