Dynamic Programming - Learn to Solve Algorithmic
Problems & Coding Challenges
-Pragya Gupta
Alumni says dynamic programming is one of his most favourite topics to teach. But
unfortunately, I feel like dynamic programming also has a reputation for being a very difficult
topic. I think dynamic programming can be very intuitive. I hope to give you all the
background knowledge you need to really crush those types of problems. In this course, on
dynamic programming , we 're going to divide the material into two main parts. Part one is
going to be about memoization. Part two will be about tabulation. We 're also going to
analyse the time and space complexity of all of our solutions. The first two numbers of the
Fibonacci sequence are exactly one. The base case is just about , you know , the first 2
numbers of the sequence. But in the recursive case, in general , what I can do is just return
the sum of the number right before the one I 'm asking for. And really, what I want to do is
give a larger number to this fib function. So if I give this code a shot, it looks like the first
three calls are correct.
Students have this habit of trying to picture everything in their mind. However, when we want
to tackle more complex problems, if we just try to capture all this information just mentally
without drawing it on, you're going to really lose track of the finer details in these structures.
So I want us to be very methodical , and we 're going to draw really how you should visualise
a problem like Fibonacci. This is actually the full recursive tree. Remember that the numbers
inside of the nodes here represent the end that we passed in. So I 'll continue to flush out
this tree , but not branch out further for the base cases. So at this point, I built out my entire
tree , and I stopped fleshing out the tree whenever we had a base case scenario. A classic
Fibonacci implementation of fib is going to be two to the n in terms of its time complexity.
But students have a hard time convincing themselves that a function like this has a two-to-
the-n power time complexity , so here we'll go through some basic understanding of time
complexity ? And I promise we 'll answer that fibonacci question.
In terms of our base case , where do we stop once we hit a number less than or equal to one
and every recursion step , we just subtract one from our current value of n. calls. So overall , I
Problems & Coding Challenges
-Pragya Gupta
Alumni says dynamic programming is one of his most favourite topics to teach. But
unfortunately, I feel like dynamic programming also has a reputation for being a very difficult
topic. I think dynamic programming can be very intuitive. I hope to give you all the
background knowledge you need to really crush those types of problems. In this course, on
dynamic programming , we 're going to divide the material into two main parts. Part one is
going to be about memoization. Part two will be about tabulation. We 're also going to
analyse the time and space complexity of all of our solutions. The first two numbers of the
Fibonacci sequence are exactly one. The base case is just about , you know , the first 2
numbers of the sequence. But in the recursive case, in general , what I can do is just return
the sum of the number right before the one I 'm asking for. And really, what I want to do is
give a larger number to this fib function. So if I give this code a shot, it looks like the first
three calls are correct.
Students have this habit of trying to picture everything in their mind. However, when we want
to tackle more complex problems, if we just try to capture all this information just mentally
without drawing it on, you're going to really lose track of the finer details in these structures.
So I want us to be very methodical , and we 're going to draw really how you should visualise
a problem like Fibonacci. This is actually the full recursive tree. Remember that the numbers
inside of the nodes here represent the end that we passed in. So I 'll continue to flush out
this tree , but not branch out further for the base cases. So at this point, I built out my entire
tree , and I stopped fleshing out the tree whenever we had a base case scenario. A classic
Fibonacci implementation of fib is going to be two to the n in terms of its time complexity.
But students have a hard time convincing themselves that a function like this has a two-to-
the-n power time complexity , so here we'll go through some basic understanding of time
complexity ? And I promise we 'll answer that fibonacci question.
In terms of our base case , where do we stop once we hit a number less than or equal to one
and every recursion step , we just subtract one from our current value of n. calls. So overall , I
