bottom-up
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 A(n)
and 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.
A:
1 |
|
B:
1 |
|
Details and Assumptions
A
is a 2D array used as the memoization table.nill
is what each item in the 2D array are initialized to.