Memoization

     

bottom-up

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.

Show explanation
View wiki
by Brilliant Staff

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
def A(n):
        if n < 3:
                return 1
        else:
                return B(n-1) + B(n-2)

def B(n):
        if n < 3:
                return 2
        else:
                return A(n-1) + B(n-2)


print B(100)

by Brilliant Staff

The code below is a solution to the classic LCS problem.

1
2
3
4
5
6
7
LCS(S,n,T,m)
{
if (n==0 or m==0) return 0
if (S[n] == T[m]) result = 1 + LCS(S,n-1,T,m-1)
else result = max( LCS(S,n-1,T,m), LCS(S,n,T,m-1) )
return result
}

It is clearly a pure recursive solution. Converting it to a top-down Dynamic Programming solution involves adding the following two lines.

A:

1
if (A[n][m] != nill) return A[n][m]

B:

1
arr[n][m] = result;

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.
Show explanation
View wiki
by Brilliant Staff
×

Problem Loading...

Note Loading...

Set Loading...