When implementing a dynamic programming solution, computing all values in a bottomup 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 topdown 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.