Class notes
Data structures- approach to dynamic programming
- Course
- Institution
this is a guide to dynamic programming in data structures and a step to how to solve algorithms.
[Show more]
Seller
Follow
pragyagupta
Content preview
Dynamic Programming - Learn to Solve AlgorithmicProblems & 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller pragyagupta. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
75323 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now