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

Monotonic Queue Optimization

1700 → 2300

1700 → 2100

You know CHT for lines. Monotonic queues handle sliding window min/max in O(1) per query.

Intro

Deque optimization for sliding window DP

The Problem

When naive DP times out

Vocabulary - Monotonic Queue

Sorted deque

Quiz: Why Monotonic

Understanding the property

The Core Idea

Why old candidates become useless

Monotonic Queue - How It Works

Add and remove

Monotonic Queue - Walkthrough

Tracing the operations

Quiz: Monotonic Queue

Knowledge check

LeetCode 239 Sliding Window Maximum - Problem Statement

LeetCode 239

Sliding Maximum - The Approach

Why sorting fails

Sliding Maximum - The Pattern

Decreasing queue

Sliding Maximum - Implementation

The code

Sliding Maximum - Walkthrough

Detailed trace

LeetCode 1696 Jump Game VI - Problem Statement

LeetCode 1696

LeetCode 1696 Jump Game VI - DP Formulation

State and transition

LeetCode 1696 Jump Game VI - Optimization

Recognizing the pattern

LeetCode 1696 Jump Game VI - Implementation

The code

LeetCode 1696 Jump Game VI - Walkthrough

DP with window constraint

Quiz: Jump Game VI

Knowledge check

Challenge: Variable Window Size

Dynamic window bounds

LeetCode 1425 Constrained Subsequence Sum - Problem Statement

LeetCode 1425

Constrained Sum - DP Formulation

The twist

Constrained Sum - Implementation

The code

Constrained Sum - Walkthrough

Maximum sum with gap constraint

LeetCode 862 Shortest Subarray with Sum at Least K - Problem Statement

LeetCode 862

Shortest Subarray - Prefix Sums

Setting up the problem

Shortest Subarray - The Idea

Monotonic increasing queue

Shortest Subarray - Implementation

The code

Shortest Subarray - Walkthrough

Tracing the prefix sum approach

Quiz: Shortest Subarray

Knowledge check

Challenge: Negative Values

Why prefix sums help

When to Use Monotonic Queue

Pattern recognition

Max Sum of Rectangle - Problem Statement

2D extension

Max Consecutive Ones III - Problem Statement

Sliding window connection

Quiz: When Monotonic Queue

Pattern recognition

Increasing vs Decreasing

Choosing the right queue

Increasing vs Decreasing - Walkthrough

Choosing the right variant

Longest Continuous Subarray - Problem Statement

With absolute diff constraint

Longest Subarray - Implementation

Two deques pattern

Challenge: Online vs Offline

Query order matters

Monotonic Queue vs Other Techniques

When to use what

Pattern - Monotonic Queue Recognition

Identifying applicable problems

Implementation Template

Reusable code structure

What's Next

Preview of Aliens Trick

Section Recap

What we learned

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

$ curl repovive.com/roadmaps/dynamic-programming

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