Domain-Specific Languages in R: Advanced Statistical Programming

© Thomas Mailund 2018

Thomas MailundDomain-Specific Languages in Rhttps://doi.org/10.1007/978-1-4842-3588-1_12

12. Dynamic Programming

Thomas Mailund¹ 

(1)

Aarhus N, Staden København, Denmark

 

As yet another example, we will create a domain-specific language for specifying dynamic programming algorithms. Dynamic programming is a technique used for speeding up recursive computations. When we need to compute a quantity from a recursion that splits into other recursions and these recursions overlap—so the computation involves evaluating the same recursive calls multiple times—we can speed up the computation by memorizing the results of the recursions. If we a priori know the values we will need to compute, we can build up a table of these values from ...