About dynamic programming (top-down method, memoization, one-dimensional)

When I'm doing paiza or AtCoder, there are quite a few things that I should be able to write as a program, but the processing time is slow and out, so I'm thinking of learning about this dynamic programming method and improving the processing speed. However, it is difficult to understand, so I will gradually verbalize it.

Definition of dynamic programming

--Use of inductive relationships --Recording of calculation results

It seems to be a general term for algorithms that satisfy (Wikipedia). For the time being, the applicable conditions etc. are omitted. To put it a little more easily, it is a method to reduce the amount of calculation by describing the inductive relationship in the form of a recurrence formula, recording the calculation result here, and calculating while referring to the result. ..

Yeah, I can't say it at all. Let's go to a concrete example (solid Fibonacci sequence). The Fibonacci sequence is a general solution of the recurrence formula expressed by a [0] = a [1] = 1, a [n] = a [n-1] + a [n-2]. (The sum of the previous two determines the value of that term)

When writing normally

fib.rb


def fib(n)
  if n <=1
    return 1
  else
    fib(n-1)+fib(n-2)
  end
end

n=gets.chomp.to_i
puts fib(n)

Like this. In this case, the amount of calculation is O (2 ^ n), and if the value assigned to n is small, there is no problem, but it becomes difficult from about 40.

When using dynamic programming (top-down)

fib2.rb


@dp=[]
def fib2(n)
  if n <= 1
    return 1
  else
    if @dp[n]
      return @dp[n]
    else
      @dp[n] = fib2(n-1)+fib2(n-2)
    end
  end
end
n=gets.chomp.to_i
puts fib2(n)

Prepare an array called @dp (n is used in an image like a hash of a key) and store the calculation results in this array. At the time of calculation, the amount of calculation becomes O (n) by referring to the value from this array, and the amount of calculation is drastically reduced. In this case, even if you substitute 10000 for n, it will be a moment.

Supplement

When defining an array, use instance variables.

Finally

I haven't been able to catch up with my understanding, so I'll try to output it in small quantities while learning a lot.

Reference article

https://ja.wikipedia.org/wiki/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95 https://www.jabba.cloud/20161020172918/

Recommended Posts

About dynamic programming (top-down method, memoization, one-dimensional)
About the method
About No Method Error
About method splitting (Java)
About the length method
Java programming (class method)
About the authenticate method.
About the map method
About the ancestors method
All about Java programming
About the to_s method.