Key Concepts

Review core concepts you need to learn to master this subject

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
  1. 1
    Dynamic 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…
  2. 2
    Storing 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 …
  3. 3
    The 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…
  4. 4
    Dynamic 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…
  5. 5
    Our 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’…
  6. 6
    With 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…
  7. 7
    Dynamic 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

Pro Logo

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory

Pro Logo