What topics does this roadmap cover?

Recursion Fundamentals, Dynamic Programming Fundamentals, 1D DP, Multi-Dimensional DP, Knapsack, Knapsack Variations, Prefix Sums, Longest Increasing Subsequence, LCS and Edit Distance, Interval DP, DP on Trees, Bitmask DP, Digit DP, Game Theory DP, Probability DP, D&C and Knuth Optimization, Convex Hull Trick, Monotonic Queue Optimization, Aliens Trick (WQS Binary Search), Slope Trick, Broken Profile DP (Plug DP)

How many units are in this roadmap?

This roadmap contains 916 units across 21 sections.

Is this roadmap free?

Yes, this roadmap is completely free.

Dynamic Programming - Roadmaps

Longest Increasing Subsequence

1300 → 1900

1500 → 1900

You've learned prefix sums. Now find the longest increasing subsequence and optimize with binary search.

Intro

The Goal

Vocabulary - Subsequence

The definition

LeetCode 300 Longest Increasing Subsequence - Problem Statement

Classic DP problem

LeetCode 300 Longest Increasing Subsequence - Why Greedy Fails

The trap

LeetCode 300 Longest Increasing Subsequence - State Design

What dp[i] means

LeetCode 300 Longest Increasing Subsequence - Transition

The recurrence

LeetCode 300 Longest Increasing Subsequence - Implementation

The code

LeetCode 300 Longest Increasing Subsequence - Walkthrough

Tracing the O(n^2) algorithm

Challenge: LIS Reconstruction

Finding the actual subsequence

Quiz: LIS State Design

Why ending at i

Quiz: LIS Basics

Knowledge check

Lessons from LIS

summary

LeetCode 300 Longest Increasing Subsequence - Binary Search Optimization

The optimization idea

LeetCode 300 Longest Increasing Subsequence - Binary Search Implementation

O(n log n) code

LeetCode 300 Longest Increasing Subsequence - Binary Search Walkthrough

O(n log n) algorithm trace

Why Binary Search Works

Understanding the tails array

Quiz: LIS Optimization

Knowledge check

LeetCode 673 Number of Longest Increasing Subsequences - Problem Statement

Counting all LIS

LeetCode 673 Number of Longest Increasing Subsequences - Dual State

Length and count

LeetCode 673 Number of Longest Increasing Subsequences - Implementation

The code

LeetCode 673 Number of Longest Increasing Subsequences - Walkthrough

Counting subsequences

Quiz: Counting LIS

When counts add up

LeetCode 354 Russian Doll Envelopes - Problem Statement

2D LIS variant

LeetCode 354 Russian Doll Envelopes - Walkthrough

2D LIS reduction

LeetCode 1048 Longest String Chain - Problem Statement

LIS on string predecessors

LeetCode 1048 Longest String Chain - Walkthrough

LIS on strings

LeetCode 368 Largest Divisible Subset - Problem Statement

LIS with divisibility

LeetCode 368 Largest Divisible Subset - The LIS Connection

Hidden pattern

LeetCode 368 Largest Divisible Subset - Implementation

The code

LeetCode 368 Largest Divisible Subset - Walkthrough

LIS with divisibility

Quiz: LIS Variants

Recognizing the pattern

Maximum Sum Increasing Subsequence - Problem Statement

Classic variation

Maximum Sum Increasing Subsequence - State Change

Sum instead of length

Maximum Sum Increasing Subsequence - Implementation

The code

Maximum Sum Increasing Subsequence - Walkthrough

Weighted LIS

Challenge: Max Sum IS Reconstruction

Finding the optimal subsequence

Longest Bitonic Subsequence - Problem Statement

Bidirectional LIS

Longest Bitonic Subsequence - Two Passes

Forward and backward

Longest Bitonic Subsequence - Implementation

The code

Longest Bitonic Subsequence - Walkthrough

Two-directional LIS

Quiz: Bitonic Structure

Understanding the approach

Minimum Deletions for Sorted - Problem Statement

LIS application

Minimum Deletions for Sorted - Implementation

LIS for non-decreasing

Pattern - LIS Family

Recognizing LIS problems

Challenge: LIS in O(n log n) Space O(n)

Understanding space usage

What's Next

Preview of LCS and Edit Distance

Section Recap

What we learned

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████