The ultimate guide to dynamic programming interviews in C++ with strategies developed by FAANG engineers. Practice with real-world questions and get interview-ready in just a few hours.

Some of the toughest questions in technical interviews require dynamic programming solutions. Dynamic programming (DP) is an advanced optimization technique applied to recursive solutions. However, DP is not a one-size-fits-all technique, and it requires practice to develop the ability to identify the underlying DP patterns. With a strategic approach, coding interview prep for DP problems shouldn’t take more than a few weeks.

This course starts with an introduction to DP and thoroughly discusses five DP patterns. You’ll learn to apply each pattern to several related problems, with a visual representation of the working of the pattern, and learn to appreciate the advantages of DP solutions over naive solutions.

After completing this course, you will have the skills you need to unlock even the most challenging questions, grok the coding interview, and level up your career with confidence.

This course is also available in JavaScript, Python, and Java—with more coming soon!

Grokking Dynamic Programming Interview in C++

# Overview

A **recursive number** is a number that can be generated from a sequence of one or more previous terms through a recurrence relation. A **recurrence relation** is an equation that uses recursion to relate the terms in a sequence. That means the $nth$ term of a sequence can be generated from its previous terms. The process of solving a computational problem by using the solutions of the smaller instances of the same problem is known as **recursion**. Recursion is calculated using recursive functions.


# Recursive Numbers

## Fibonacci Numbers
## Staircase Problem
## Number Factors
## Count Ways to Score in a Game
## Unique Paths to Goal
## Nth Tribonacci Number
## Catalan Numbers
## House Thief
## Minimum Jumps to Reach End
## Minimum Jumps with Fee
## Matrix Chain Multiplication

A **recursive function** is a function that calls itself with a reduced problem set.
A recursive function has the following:

1. The base case, a trivial case that can be solved easily
2. The recursive case, a case that implements the recurrence relation

An example of recurrence relation for finding the $nth$ term using its previous two terms can be:

$F_{n}=F_{n-1}+F_{n-2}$

with base conditions as:

* $F_{0}=0$
* $F_{1}=1$

So, if we want to find $F_4$ using the above recurrence relation, the equation will be:

$F_4=F_3+F_2$ 

To calculate $F_4$ we need $F_3$ and $F_2$:

$F_3=F_2+F_1$

$F_2=F_1+F_0$

After filling in the values of the base conditions for calculating $F_2$:

$F_2=(1)+(0)=1$

$F_3=(1)+(1)=2$

$F_4=(2)+(1)=3$





  

  

# Examples

Let's get introduced to the Recursive Numbers pattern.


Introduction to Recursive Numbers

Let's get introduced to the Recursive Numbers pattern.

Getting Started

0/1 Knapsack

Unbounded Knapsack

Recursive Numbers

Longest Common Substring

Palindromic Subsequence

Conclusion

Introduction to Recursive Numbers

Overview