Technical Interview Techniques: Dynamic Programming
Dynamic Programming is a technique we can apply to difficult questions that ask us to maximize a value given many options or constraints.
Start
Key Concepts
Review core concepts you need to learn to master this subject
Dynamic Programming Optimal Substructure
Dynamic Programming
Dynamic Programming
Dynamic Programming Problem Variable
Dynamic Programming Optimal Substructure
Dynamic Programming Optimal Substructure
A problem has optimal substructure if its sub-problems have optimal solutions that constitute the problem’s optimal solution. This type of problem can be solved using dynamic programming.
Technical Interview Problems: Dynamic Programming
Lesson 1 of 1
- 1Dynamic programming is an optimization strategy for designing algorithms. The technique is beneficial for technical interviews because solving problems with an optimal big O runtime will improve yo…
- 2Storing answers to sub-problems is an essential aspect of dynamic programming. Let’s explore why this is the case. The Fibonacci Sequence is a series of numbers where the next number equals the …
- 3The Fibonacci sequence is a perfect case to apply dynamic programming. Each Fibonacci number relies on two previous numbers, and those numbers never change. We have overlapping sub-problems! W…
- 4Dynamic programming is especially helpful for problems where there are many different options and we have a particular goal we’re trying to maximize. For the sake of learning, we’re going to imagi…
- 5Our brute force approach is inefficient! We’re compounding work by creating many different combinations that contain the same items. Just like with Fibonacci, we’re repeating computations that won’…
- 6With our grid built, we only need to fill it in to find our optimal value. Remember: each column is the capacity of a knapsack and each row is an item we can add. The first row is “no item” and the…
- 7Dynamic programming is a technique to optimize solutions for problems which have a structure that involves repeated, identical computations. For dynamic programming to work, it’s essential that t…
What you'll create
Portfolio projects that showcase your new skills
How you'll master it
Stress-test your knowledge with quizzes that help commit syntax to memory