# Lesson 4 - Recursion and Dynamic Programming

Please visit the Lesson Page for more detailed info

Session Recordings:
English: https://youtu.be/bCPsBxEyQgc
Hindi: https://youtu.be/c6AYl5bONRI

This lecture covers recursion, memoization, and dynamic programming. We look at two common problems in dynamic programming: longest common subsequences and knapsack problems.

### Notebooks used in this lesson:

I didn’t quite understand the `recurese(0,0)` call in the `lcs_memo` function.
Can anyone explain?

Has anyone worked out how to return all the items in the knapsack using recursion? I’ve been trying to work it out for a few hours and I just keep digging a bigger hole for myself. I’ve searched online and can’t find an answer there either.

I think you are asking how this line of code…return max(option1, option2) work in max_profit_recursive function? right?

The challenge exercise is to alter the function so that it returns the best list of items in the knapsack as well.

1 Like

Oh the knapsack memoization solution?..i can share an online lecture on knapsack memoization…https://youtu.be/dT6dvdbpChA. And i also need to work on it too. Sorry for late reply. Thanks

Maybe you can look at this link:

With its help, I created a function to return a list of tuples indicating the weight and the profit of elements selected.

Hope this help.

same. if you know could you explain now?

Can you please explain how the time complexity of the recursive solution is 2^(m+n) ? I am not able to understand the m + n part.

m and n are the lengths of the given two strings.

Since for the worst-case scenario, the LCS would be zero.
Therefore, both the strings would generate 2 strings at every step.

So, the time complexity would be 2^m.2^n = 2^(m+n).
i.e. O(2^(m+n))

Since m and n are assumed to be Indefinitely large numbers.
We can say m+n = N where N is an indefinitely large number

Therefore, the time complexity for the worst-case scenario would essentially be
O(2^N).

1 Like