Memoization #

Elements of dynamic programming #

Longest common subsequence #

• base cases along left and top edge

• see which subproblems are needed to solve current sub problem

• our next level after base cases is the top left corner

• nested loops

• another order to solve

• can also go by columns

• overall runtime is \( \Theta(n) \) where \( n = i + j \) , the sum of the 2 sequences

 0  0  0  0  0  0  0 
 0  0  0  0  1  1  1 
 0  1  1  1  1  2  2 
 0  1  1  2  2  2  2 
 0  1  1  2  2  3  3 
 0  1  2  2  2  3  3 
 0  1  2  2  3  3  4 
 0  1  2  2  3  4  4 

b c b a 

Improving the space complexity #

• we can overwrite the first 2 rows each pass thru