Transcription of Dynamic Programming
1 Potes enim videre in hac margine, qualiter hoc operati fuimus, scilicet quodiunximus primum numerum cum secundo, videlicet cum ; et secundum cumtercio; et tercium cum quarto; et quartum cum quinto, et sic [You can see in the margin here how we have worked this; clearly, we combined the rst number with the second, namely with , and the second with the third, andthe third with the fourth, and the fourth with the fth, and so ] LeonardoPisano,Liber Abaci( )Those who cannot remember the past are condemned to repeat it. JorgeAgust nNicol sRuizdeSantayanayBorr s,The Life of Reason, Book I: Introduction and Reason in Common Sense( )You know what a learning experience is?Alearningexperienceisoneofthosethings thatsays, You know that thing you just did? Don t do that. DouglasAdams,The Salmon of Doubt( ) Dynamic Programming .
2 M atr of the earliest examples of recursion arose in India more than years ago,in the study of poetic meter, or prosody. Classical Sanskrit poetry distinguishesbetween two types of syllables ( ):light(laghu) andheavy(guru). Inone class of meters, variously calledm atr atr achandas, each line ofpoetry consists of a fixed number of beats (m atr a), where each light syllablelasts one beat and each heavy syllable lasts two beats. The formal study ofm atr back to theChandah. astra, written by the scholar Pi ngalabetween and .Pi ngala observed that there are exactly five4-beat meters: , , , , and . (Here each represents a long syllable and each represents a short syllable.) In Morse code, a dah lasts three times as long as a dit , but each dit or dah is followedby a pause with the same duration as a dit.
3 Thus, each dit-pause is alaghu , each .D P Although Pi ngala s texthintsat a systematic rule for counting meters with agiven number of beats, it took about a millennium for that rule to be statedexplicitly. In the th century , another Indian scholar named Virah wrotea commentary on Pi ngala s work, in which he observed that the number ofmeters withnbeats is the sum of the number of meters with(n 2)beats andthe number of meters with(n 1)beats. In more modern notation, Virah sobservation implies a recurrence for the total numberM(n)ofn-beat meters:M(n)=M(n 2)+M(n 1)It is not hard to see thatM(0)=1(there is only one empty meter) andM(1)=1(the only one-beat meter consists of a single short syllable).The same recurrence reappeared in Europe about years after Virah ,in Leonardo of Pisa s treatiseLiber Abaci, one of the most influentialearly European works on algorism.
4 In full compliance with Stigler s Lawof Eponymy, the modernFibonacci numbersare defined using Virah srecurrence, but with di erent base cases:Fn=8> <>:0ifn=01ifn=1Fn 1+Fn 2otherwiseIn particular, we haveM(n)=Fn+1for Can Be SlowThe recursive definition of Fibonacci numbers immediately gives us a recur-sive algorithm for computing them. Here is the same algorithm written inpseudocode: dah-pause is aguru , and there are exactly five letters (M,D,R,U, andH) whose codes lastfourm atr a. TheChandah. astracontainstwosystematic rules for listing all meters with a given numberofsyllables, which correspond roughly to writing numbers in binary from left to right (likeGreeks) or from right to left (like Egyptians). The same text includes a recursive algorithm tocompute2n(the number of meters withnsyllables) by repeated squaring, and (arguably) arecursive algorithm to compute binomial coe cients (the number of meters withkshort syllablesandnsyllables overall).
5 No scientific discovery is named after its original discoverer. In his paper that gives thelaw its name, the statistician Stephen Stigler jokingly claimed that this law was first proposed bysociologist Robert K. Merton. However, similar statements were previously made by VladimirArnol d in the s ( Discoveries are rarely attributed to the correct person. ), Carl Boyer in ( Clio, the muse of history, often is fickle in attaching names to theorems! ), Alfred NorthWhitehead in ( Everything of importance has been said before by someone who did notdiscover it. ), and even Stephen s father George Stigler in ( If we should ever encounter acase where a theory is named for the correct man, it will be noted. ). We will seemanyotherexamples of Stigler s law in this book. 8 .. M atr F (n):ifn=0return0else ifn=1return1elsereturnR F (n 1)+R F (n 2)Unfortunately, this naive recursive algorithm is horribly slow.
6 Except for therecursive calls, the entire algorithm requires only a constant number of steps:one comparison and possibly one addition. LetT(n)denote the number ofrecursive calls toR F ; this function satisfies the recurrenceT(0)=1,T(1)=1,T(n)=T(n 1)+T(n 2)+1,which looks an awful lot like the recurrence for Fibonacci numbers them-selves! Writing out the first several values ofT(n)suggests the closed-formsolutionT(n)=2Fn+1 1, which we can verify by induction (hint, hint). SocomputingFnusing this algorithm takes about twice as long as just countingtoFn. Methods beyond the scope of this book imply thatFn= ( n), where =(p5+1)/2 the so-calledgolden ratio. In short, the runningtime of this recursive algorithm is exponential can actually see this exponential growth directly as follows. Think of therecursion tree forR F as a binary tree of additions, with only0s and1sat the leaves.
7 Since the eventual output isFn, exactlyFnof the leaves musthave value1; these leaves represent the calls toR R (1). An easy inductiveargument (hint, hint) implies thatR F (0)is called exactlyFn 1times. (Ifwe just want an asymptotic bound, it s enough to observe that the numberof calls toR F (0)is at most the number of calls toR F (1).) Thus,the recursion tree has exactlyFn+Fn 1=Fn+1=O(Fn)leaves, and therefore,because it s a full binary tree,2Fn+1 1=O(Fn)nodes (r)ization: Remember EverythingThe obvious reason for the recursive algorithm s lack of speed is that it com-putes the same Fibonacci numbers over and over and over. A single call toR F (n)results in one recursive call toR F (n 1), two recursive callstoR F (n 2), three recursive calls toR F (n 3), five recursive callstoR F (n 4), and in generalFk 1recursive calls toR F (n k)forany integer0 k<n.
8 Each call is recomputing some Fibonacci number can speed up our recursive algorithm considerably by writing down theresults of our recursive calls and looking them up again if we need them later. notes on solving backtracking recurrences..D P F5F3F4F2F1F1F0F3F2F1F1F0F2F1F0F4F3F2F1F1 F0F2F1F0F6F5F3F4F2F1F1F0F3F2F1F1F0F2F1F0 F7 Figure ..The recursion tree for computingF7; optimization technique, now known asmemoization(yes, without an R), isusually credited to Donald Michie in , but essentially the same techniquewas proposed in by Arthur Samuel. M F (n):ifn=0return0else ifn=1return1elseifF[n]is undefinedF[n] M F (n 1)+M F (n 2)returnF[n]Memoization clearly decreases the running time of the algorithm, but byhow much? If we actually trace through the recursive calls made byM F ,we find that the arrayF[]is filled from the bottom up: firstF[2], thenF[3],and so on, up toF[n].
9 This pattern can be verified by induction: Each entryF[i]is filled only after its predecessorF[i 1]. If we ignore the time spent inrecursive calls, it requires only constant time to evaluate the recurrence for eachFibonacci numberFi. But by design, the recurrence forFiis evaluated only oncefor each indexi. We conclude thatM F performs onlyO(n)additions, anexponentialimprovement over the na ve recursive algorithm! Michie proposed that Programming languages should support an abstraction he called a memo function , consisting of both a standard function ( rule ) and a dictionary ( rote ), insteadof separately supporting arrays and functions. Whenever a memo function computes a functionvalue for the first time, it memorises (yes, with an R) that value into its dictionary. Michie wasinspired by Samuel s use of rote learning to speed up the recursive evaluation of checkers gametrees; Michie describes his more general proposal as enabling the programmer to Samuelize anyfunctions he pleases.
10 (As far as I can tell, Michie never used the term memoisation himself.)Memoization was used even earlier by Claude Shannon s maze-solving robot Theseus , whichhe designed and constructed in .. M atr ..The recursion tree forF7trimmed by memoization. Downward green arrows indicate writinginto the memoization array; upward red arrows indicate reading from the memoization Programming : Fill DeliberatelyOnce we see how the arrayF[]is filled, we can replace the memoized recurrencewith a simple for-loop thatintentionallyfills the array in that order, instead ofrelying on a more complicated recursive algorithm to do it for us F (n):F[0] 0F[1] 1fori 2tonF[i] F[i 1]+F[i 2]returnF[n]Now the time analysis is immediate:I F clearly usesO(n)additionsandstoresO(n) is our first explicitdynamic programmingalgorithm.
