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/