Key Concepts
Review core concepts you need to learn to master this subject
Dynamic Programming
Dynamic Programming
Dynamic programming is both a mathematical optimization method and a computer programming method. It simplifies a complicated problem by breaking it down into simpler sub-problems.
It can be applied to combinatorial and optimization problems such as finding the shortest path between two points or finding the smallest set of objects that satisfies some criteria.
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