Lesson 4 - Recursion and Dynamic Programming

Please visit the Lesson Page for more detailed info :point_up:

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

:zap: 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:

:question: Asking/Answering Questions :
Reply to this thread to ask questions. Before asking, scroll through the thread and check if your question (or a similar one) is already present. If yes, just like it. We will give priority to the questions with the most likes. The rest will be answered by our mentors or the community. If you see a question you know the answer to, please post your answer as a reply to that question. Let’s help each other learn!

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