Concept
Dynamic programming applies when a problem breaks into subproblems that repeat and whose answers combine into the whole. Spotting the repeated subproblem and writing its recurrence is most of the work.
The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.
A few lines that show Overlapping subproblems doing its job.
# ways(n): ways to climb n steps taking 1 or 2 at a time
# ways(n) = ways(n - 1) + ways(n - 2) <- the recurrence
# ways(5) asks ways(3) twice, ways(2) three times...
def ways(n, memo={}):
if n <= 1:
return 1
if n not in memo:
memo[n] = ways(n - 1) + ways(n - 2)
return memo[n]Jumping to a table before the recurrence is right. Write the recursive definition and check it on tiny inputs first; the table is only an optimisation of a correct recursion.
Your roadmap puts these before Overlapping subproblems, unless you already know them.
Once a session shows you understand Overlapping subproblems, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.
Topics that build on Overlapping subproblems.