The ultimate dynamic programming guide by FAANG engineers. Structured prep with real-world DP questions to get interview-ready in hours!

New Dynamic Programming Interview-Python.png

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, C++, and Java—with more coming soon!

Grokking Dynamic Programming Interview in Python

# Statement

Suppose you are given an array, `nums`, containing positive integers. You need to find the length of the longest bitonic subsequence in this array. A bitonic subsequence can be of the following three types:

- It can consist of numbers that are first increasing and then decreasing. For example, $(2, 6, 9, 3, 2)$.

- It can consist of numbers that are only increasing (where the decreasing part at the end is empty). For example, $(2, 3, 7, 9)$.

- It can consist of numbers that are only decreasing (where the increasing part at the start is empty). For example,  $(15, 12, 5, 3, 2, 1)$.

Let's say you have the following array:
- $[19, 20, 5, 3, 13]$

The longest bitonic subsequence from this array is $(19, 20, 5, 3)$, and the length of this subsequence is $4$.



**Constraints:**

- $1\leq$ `nums.length` $\leq 900$
- $1\leq$` nums[i]` $\leq 10^4$

# Examples

  

Let's solve the Longest Bitonic Subsequence problem using Dynamic Programming.

Getting Started

0/1 Knapsack

Unbounded Knapsack

Recursive Numbers

Longest Common Substring

Palindromic Subsequence

Conclusion

Longest Bitonic Subsequence