When implementing a dynamic programming solution, computing all values in a bottom-up fashion(tabulation) is asymptotically faster than using recursion and memoization.
The following python function computes two sequences
B(n). Unfortunately, it is very slow. You're task is to memoize the two functions. What are the last three digits of the output of the program?`
1 2 3 4 5 6 7 8 9 10 11 12 13 14
The code below is a solution to the classic LCS problem.
1 2 3 4 5 6 7
It is clearly a pure recursive solution. Converting it to a top-down Dynamic Programming solution involves adding the following two lines.
Details and Assumptions
Ais a 2D array used as the memoization table.
nillis what each item in the 2D array are initialized to.