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.
--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)
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.
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.
When defining an array, use instance variables.
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.
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