[RUBY] À propos de la méthode de planification dynamique (méthode descendante, conversion de mémo, unidimensionnel)

Quand je fais paiza ou AtCoder, il y a pas mal de choses que je devrais être capable d'écrire en tant que programme, mais le temps de traitement est lent et épuisé, donc je pense à apprendre cette méthode de planification dynamique et à améliorer la vitesse de traitement. Cependant, c'est difficile à comprendre, je vais donc le verbaliser progressivement.

Définition de la méthode de planification dynamique

--Utilisation de relations inductives --Enregistrement des résultats des calculs

Cela semble être un terme général pour les algorithmes qui satisfont (Wikipedia). Pour le moment, les conditions applicables, etc. seront omises. Pour faciliter la compréhension, il s'agit d'une méthode pour réduire la quantité de calcul en décrivant la relation inductive sous la forme d'une expression graduelle, en enregistrant ici le résultat du calcul et en calculant en se référant au résultat. ..

Ouais, je ne peux pas le dire d'une manière facile à comprendre. Passons à un exemple concret (séquence de nombres de Fibonacci solide). La séquence de nombres de Fibonacci est une solution générale de l'équation graduelle représentée par a [0] = a [1] = 1, a [n] = a [n-1] + a [n-2]. (La somme des deux précédents détermine la valeur de ce terme)

Lorsque vous écrivez normalement

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)

Comme ça. Dans ce cas, la quantité de calcul est O (2 ^ n), et si la valeur attribuée à n est petite, il n'y a pas de problème, mais cela devient difficile à partir d'environ 40.

Lors de l'utilisation de la planification dynamique (descendante)

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)

Préparez un tableau appelé @dp (n est utilisé dans une image comme le hachage d'une clé) et stockez les résultats du calcul dans ce tableau. Au moment du calcul, la quantité de calcul devient O (n) en se référant aux valeurs de ce tableau, et la quantité de calcul est considérablement réduite. Dans ce cas, même si vous remplacez 10000 par n, ce sera un instant.

Supplément

Lors de la définition d'un tableau, utilisez des variables d'instance.

finalement

Je n'ai pas été en mesure de rattraper ma compréhension, alors je vais essayer de le produire en petites quantités tout en apprenant beaucoup.

Article de référence

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/