Loading repovive.com/roadmaps/dynamic-programming
Roadmaps
Dynamic Programming
Broken Profile DP (Plug DP)
Problemset
Discussion
AI Helper
Recursion Fundamentals
0/42
1
Intro
2
Core Concept
3
Vocabulary - Base Case
4
Vocabulary - Recursive Case
5
Factorial - Problem Statement
6
Quiz: Base Case
7
Factorial - Base Case
8
Factorial - Recursive Formula
9
Factorial - Implementation
10
Factorial - Walkthrough
11
Visualization - Call Stack
12
Quiz: Call Stack
13
Lessons from Factorial
14
Sum of Digits - Problem Statement
15
Quiz: Recursive Structure
16
Sum of Digits - Base Case
17
Sum of Digits - Recursive Formula
18
Sum of Digits - Implementation
19
Sum of Digits - Walkthrough
20
GCD - Problem Statement
21
Quiz: GCD
22
GCD - The Key Observation
23
GCD - Base Case
24
GCD - Recursive Formula
25
GCD - Implementation
26
GCD - Walkthrough
27
Challenge: Trace GCD
28
Power Function - Problem Statement
29
Quiz: Power Function
30
Power Function - Naive Recursion
31
Power Function - The Optimization
32
Power Function - Base Cases
33
Power Function - Implementation
34
Power Function - Walkthrough
35
Quiz: Optimized Power
36
Lessons from Recursion
37
Pattern - Recursive Decomposition
38
Common Recursion Mistakes
39
Recursion vs Iteration
40
Quiz: Recursion vs Iteration
41
What's Next
42
Section Recap
Dynamic Programming Fundamentals
0/45
1
Intro
2
LeetCode 509 Fibonacci - Problem Statement
3
LeetCode 509 Fibonacci - Base Cases
4
LeetCode 509 Fibonacci - Recursive Formula
5
LeetCode 509 Fibonacci - Naive Implementation
6
Visualization - Fibonacci Tree
7
Vocabulary - Overlapping Subproblems
8
Time Complexity - Exponential Growth
9
The Main Idea
10
Socratic Checkpoint
11
Recursion to DP
12
What Is Memoization?
13
Vocabulary - Top-Down DP
14
LeetCode 509 Fibonacci - Memoization Setup
15
LeetCode 509 Fibonacci - Memoized Code
16
Memoization - Time Complexity
17
Memoization - Space Complexity
18
LeetCode 70 Climbing Stairs - Problem Statement
19
LeetCode 70 Climbing Stairs - Recursive Intuition
20
LeetCode 70 Climbing Stairs - Memoized Solution
21
LeetCode 70 Climbing Stairs - Implementation
22
Quiz: Memoization Complexity
23
Lessons from Memoization
24
What Is Tabulation?
25
Vocabulary - Bottom-Up DP
26
LeetCode 509 Fibonacci - Tabulation Implementation
27
Space Optimization
28
LeetCode 509 Fibonacci - O(1) Space
29
Top-Down vs Bottom-Up
30
LeetCode 746 Min Cost Climbing Stairs - Problem Statement
31
LeetCode 746 Min Cost Climbing Stairs - State Definition
32
LeetCode 746 Min Cost Climbing Stairs - Transition
33
LeetCode 746 Min Cost Climbing Stairs - Implementation
34
LeetCode 152 Maximum Product Subarray - Problem Statement
35
LeetCode 152 Maximum Product Subarray - Why It's Tricky
36
LeetCode 152 Maximum Product Subarray - Tracking Two States
37
LeetCode 152 Maximum Product Subarray - Implementation
38
Quiz: Simple DP Patterns
39
LeetCode 91 Decode Ways - Problem Statement
40
LeetCode 91 Decode Ways - The Choices
41
LeetCode 91 Decode Ways - Edge Cases
42
LeetCode 91 Decode Ways - State Definition
43
LeetCode 91 Decode Ways - Transition
44
LeetCode 91 Decode Ways - Implementation
45
Section Recap
1D DP
0/41
1
Intro
2
From Memoization to Problems
3
DP Pattern and Importance
4
LeetCode 198 House Robber - Problem Statement
5
LeetCode 198 House Robber - Why Greedy Fails
6
LeetCode 198 House Robber - Defining the DP
7
LeetCode 198 House Robber - Transition
8
LeetCode 198 House Robber - Base Cases
9
LeetCode 198 House Robber - Final Answer
10
LeetCode 198 House Robber - Implementation
11
Quiz: House Robber State
12
Lessons from House Robber
13
Codeforces 455A Boredom - Problem Statement
14
Codeforces 455A Boredom - Defining the DP
15
Codeforces 455A Boredom - Transition
16
Codeforces 455A Boredom - Base Cases
17
Codeforces 455A Boredom - Final Answer
18
Codeforces 455A Boredom - Implementation
19
Quiz: Boredom Reduction
20
Codeforces 977F Consecutive Subsequence - Problem Statement
21
Codeforces 977F Consecutive Subsequence - State Definition - 1
22
Codeforces 977F Consecutive Subsequence - State Definition - 2
23
Codeforces 977F Consecutive Subsequence - Transition
24
Codeforces 977F Consecutive Subsequence - Base Cases
25
Codeforces 977F Consecutive Subsequence - Final Answer and Reconstruction
26
Codeforces 977F Consecutive Subsequence - Implementation
27
Quiz: Consecutive Subsequence
28
Vocabulary - State Compression
29
Lessons from Boredom and Consecutive Subsequence
30
Pattern - Adjacent Blocking
31
Challenge: Trace Boredom
32
Quiz: 1D DP Patterns
33
Codeforces 1741E Sending a Sequence - Problem Statement
34
Codeforces 1741E Sending a Sequence - From Intuition to Prefix States
35
Codeforces 1741E Sending a Sequence - Defining the State and Base Case
36
Codeforces 1741E Sending a Sequence - Determining the Final Answer
37
Codeforces 1741E Sending a Sequence - Transition Case 1
38
Codeforces 1741E Sending a Sequence - Transition Case 2
39
Practice - Maximum Points
40
What's Next
41
Section Recap
Multi-Dimensional DP
0/40
1
Intro
2
Why One Dimension Fails
3
What Is Multi-Dimensional DP?
4
Vocabulary - 2D State
5
The Same Four Steps
6
Quiz: When to Add Dimensions
7
Codeforces 478D Red Green Towers - Problem Statement
8
Codeforces 478D Red Green Towers - The Setup
9
Codeforces 478D Red Green Towers - Finding the Height
10
Codeforces 478D Red Green Towers - State Definition
11
Codeforces 478D Red Green Towers - Transition
12
Codeforces 478D Red Green Towers - Base Cases
13
Codeforces 478D Red Green Towers - Final Answer
14
Codeforces 478D Red Green Towers - Implementation
15
Lessons from Red Green Towers
16
Grid 1 - Problem Statement
17
Grid 1 - Understanding the Grid
18
Grid 1 - State Definition
19
Grid 1 - Transition
20
Grid 1 - Handling Walls
21
Grid 1 - Base Cases
22
Grid 1 - Implementation
23
Lessons from Grid 1
24
Edit Distance - Problem Statement
25
Edit Distance - The Three Operations
26
Edit Distance - State Definition
27
Edit Distance - Transition
28
Edit Distance - Base Cases
29
Edit Distance - Implementation
30
Lessons from Edit Distance
31
Grid Paths - Problem Statement
32
Grid Paths - The Setup
33
Grid Paths - State Definition
34
Grid Paths - Transition
35
Grid Paths - Implementation
36
LeetCode 64 Minimum Path Sum - Problem Statement
37
LeetCode 64 Minimum Path Sum - State Definition
38
LeetCode 64 Minimum Path Sum - Transition
39
LeetCode 64 Minimum Path Sum - Implementation
40
Section Recap
Knapsack
0/43
1
Intro
2
0/1 Knapsack - Problem Statement
3
0/1 Knapsack - Why Greedy Fails
4
0/1 Knapsack - State Design
5
0/1 Knapsack - Base Cases
6
0/1 Knapsack - Transition
7
0/1 Knapsack - Final Answer
8
0/1 Knapsack - Implementation
9
0/1 Knapsack - Walkthrough
10
Lessons from 0/1 Knapsack
11
Challenge: Reconstruct Items
12
Quiz: 0/1 Knapsack Concepts
13
Applying 0/1 Knapsack
14
Weight-Based to Value-Based
15
Knapsack 2 - Problem Statement
16
Knapsack 2 - Why Weight-Based DP Fails
17
Knapsack 2 - The Observation
18
Knapsack 2 - State Design
19
Knapsack 2 - Transition
20
Knapsack 2 - Implementation
21
Knapsack 2 - Walkthrough
22
Lessons from Value-Based Knapsack
23
Quiz: When to Use Value-Based
24
Quiz: Knapsack State Design
25
0/1 to Unbounded
26
Unbounded Knapsack - Problem Statement
27
Unbounded Knapsack - State Design
28
Unbounded Knapsack - Transition
29
Unbounded Knapsack - Implementation
30
Unbounded Knapsack - Walkthrough
31
Lessons from Unbounded Knapsack
32
Quiz: 0/1 vs Unbounded
33
LeetCode 322 Coin Change - Problem Statement
34
LeetCode 322 Coin Change - Walkthrough
35
Quiz: Knapsack Variations
36
Pattern - Knapsack DP
37
Book Shop - Problem Statement
38
Book Shop - Recognizing the Pattern
39
Book Shop - State Design
40
Book Shop - Walkthrough
41
Book Shop - Implementation
42
What's Next
43
Section Recap
Knapsack Variations
0/46
1
Intro
2
Max Value to True/False
3
LeetCode 416 Partition Equal Subset Sum - Problem Statement
4
LeetCode 416 Partition Equal Subset Sum - The Hidden Knapsack
5
LeetCode 416 Partition Equal Subset Sum - Boolean State Design
6
LeetCode 416 Partition Equal Subset Sum - Implementation
7
LeetCode 416 Partition Equal Subset Sum - Walkthrough
8
Lessons from Partition
9
Challenge: Partition Reconstruction
10
Quiz: Subset Sum Basics
11
LeetCode 494 Target Sum - Problem Statement
12
LeetCode 494 Target Sum - Converting Signs to Subsets
13
LeetCode 494 Target Sum - Implementation
14
LeetCode 494 Target Sum - Walkthrough
15
Quiz: Target Sum Transform
16
Finding One to Counting All
17
LeetCode 518 Coin Change II - Problem Statement
18
LeetCode 518 Coin Change II - Combinations vs Permutations
19
LeetCode 518 Coin Change II - Loop Order
20
LeetCode 518 Coin Change II - Implementation
21
LeetCode 518 Coin Change II - Walkthrough
22
Lessons from Counting Knapsack
23
Challenge: Combinations vs Permutations
24
Quiz: Counting in DP
25
Unlimited to Limited
26
Bounded Knapsack - Problem Statement
27
Bounded Knapsack - Why Naive Is Slow
28
Bounded Knapsack - Binary Representation
29
Bounded Knapsack - Implementation
30
Bounded Knapsack - Walkthrough
31
Quiz: Binary Splitting
32
Quiz: Knapsack Types
33
One Constraint to Two
34
LeetCode 474 Ones and Zeroes - Problem Statement
35
LeetCode 474 Ones and Zeroes - Two Capacities
36
LeetCode 474 Ones and Zeroes - Implementation
37
LeetCode 474 Ones and Zeroes - Walkthrough
38
LeetCode 1049 Last Stone Weight II - Problem Statement
39
LeetCode 1049 Last Stone Weight II - Hidden Subset Sum
40
LeetCode 1049 Last Stone Weight II - Implementation
41
LeetCode 1049 Last Stone Weight II - Walkthrough
42
Quiz: Last Stone Reduction
43
Practice - Subset Sum Count
44
What's Next
45
Pattern - Choosing the Right Variation
46
Section Recap
Prefix Sums
0/44
1
Intro
2
The Range Sum Problem
3
Naive Approach
4
Vocabulary - Prefix Sum
5
Building the Prefix Array
6
Answering Range Queries
7
Prefix Sums - Implementation
8
Prefix Sums - Walkthrough
9
Challenge: Off-by-One Errors
10
Quiz: Prefix Sums Basics
11
Static Range Sum Queries - Problem Statement
12
Static Range Sum Queries - Why Prefix Sums
13
Codeforces 869B Kuriyama Mirai's Stones - Problem Statement
14
Static Range Sum Queries - The Formula
15
Codeforces 869B Kuriyama Mirai's Stones - Two Arrays
16
Static Range Sum Queries - Walkthrough
17
Codeforces 869B Kuriyama Mirai's Stones - Walkthrough
18
Quiz: Range Query Complexity
19
Static Range Sum Queries - Implementation
20
Codeforces 869B Kuriyama Mirai's Stones - Implementation
21
LeetCode 560 Subarray Sum Equals K - Problem Statement
22
LeetCode 560 Subarray Sum Equals K - HashMap Trick
23
LeetCode 560 Subarray Sum Equals K - Implementation
24
LeetCode 560 Subarray Sum Equals K - Walkthrough
25
Challenge: Subarray Sum Zero
26
Quiz: Prefix Sum + HashMap
27
LeetCode 238 Product of Array Except Self - Problem Statement
28
LeetCode 238 Product of Array Except Self - Prefix and Suffix
29
LeetCode 238 Product of Array Except Self - Walkthrough
30
Quiz: Product Edge Cases
31
LeetCode 238 Product of Array Except Self - Space Optimization
32
LeetCode 304 Range Sum Query 2D - Problem Statement
33
LeetCode 304 Range Sum Query 2D - The Concept
34
LeetCode 304 Range Sum Query 2D - Walkthrough
35
Challenge: 2D Submatrix Count
36
LeetCode 304 Range Sum Query 2D - Implementation
37
Quiz: 2D Prefix Sums
38
LeetCode 53 Maximum Subarray Sum - Problem Statement
39
LeetCode 53 Maximum Subarray Sum - Implementation
40
Quiz: Kadane vs Prefix
41
Lessons from Prefix Sums
42
Pattern - When to Use Prefix Sums
43
What's Next
44
Section Recap
Longest Increasing Subsequence
0/47
1
Intro
2
Vocabulary - Subsequence
3
LeetCode 300 Longest Increasing Subsequence - Problem Statement
4
LeetCode 300 Longest Increasing Subsequence - Why Greedy Fails
5
LeetCode 300 Longest Increasing Subsequence - State Design
6
LeetCode 300 Longest Increasing Subsequence - Transition
7
LeetCode 300 Longest Increasing Subsequence - Implementation
8
LeetCode 300 Longest Increasing Subsequence - Walkthrough
9
Challenge: LIS Reconstruction
10
Quiz: LIS State Design
11
Quiz: LIS Basics
12
Lessons from LIS
13
LeetCode 300 Longest Increasing Subsequence - Binary Search Optimization
14
LeetCode 300 Longest Increasing Subsequence - Binary Search Implementation
15
LeetCode 300 Longest Increasing Subsequence - Binary Search Walkthrough
16
Why Binary Search Works
17
Quiz: LIS Optimization
18
LeetCode 673 Number of Longest Increasing Subsequences - Problem Statement
19
LeetCode 673 Number of Longest Increasing Subsequences - Dual State
20
LeetCode 673 Number of Longest Increasing Subsequences - Implementation
21
LeetCode 673 Number of Longest Increasing Subsequences - Walkthrough
22
Quiz: Counting LIS
23
LeetCode 354 Russian Doll Envelopes - Problem Statement
24
LeetCode 354 Russian Doll Envelopes - Walkthrough
25
LeetCode 1048 Longest String Chain - Problem Statement
26
LeetCode 1048 Longest String Chain - Walkthrough
27
LeetCode 368 Largest Divisible Subset - Problem Statement
28
LeetCode 368 Largest Divisible Subset - The LIS Connection
29
LeetCode 368 Largest Divisible Subset - Implementation
30
LeetCode 368 Largest Divisible Subset - Walkthrough
31
Quiz: LIS Variants
32
Maximum Sum Increasing Subsequence - Problem Statement
33
Maximum Sum Increasing Subsequence - State Change
34
Maximum Sum Increasing Subsequence - Implementation
35
Maximum Sum Increasing Subsequence - Walkthrough
36
Challenge: Max Sum IS Reconstruction
37
Longest Bitonic Subsequence - Problem Statement
38
Longest Bitonic Subsequence - Two Passes
39
Longest Bitonic Subsequence - Implementation
40
Longest Bitonic Subsequence - Walkthrough
41
Quiz: Bitonic Structure
42
Minimum Deletions for Sorted - Problem Statement
43
Minimum Deletions for Sorted - Implementation
44
Pattern - LIS Family
45
Challenge: LIS in O(n log n) Space O(n)
46
What's Next
47
Section Recap
LCS and Edit Distance
0/41
1
Intro
2
Two-Dimensional State
3
LeetCode 1143 Longest Common Subsequence - Problem Statement
4
LeetCode 1143 Longest Common Subsequence - State Design
5
LeetCode 1143 Longest Common Subsequence - Transition
6
LeetCode 1143 Longest Common Subsequence - Implementation
7
LeetCode 1143 Longest Common Subsequence - Walkthrough
8
Quiz: LCS Concepts
9
LeetCode 1143 Longest Common Subsequence - Reconstruction
10
Lessons from LCS
11
Challenge: LCS Space Optimization
12
LeetCode 712 Minimum ASCII Delete Sum for Two Strings - Problem Statement
13
LeetCode 712 Minimum ASCII Delete Sum for Two Strings - Weighted DP
14
LeetCode 712 Minimum ASCII Delete Sum for Two Strings - Implementation
15
LeetCode 712 Minimum ASCII Delete Sum for Two Strings - Walkthrough
16
LeetCode 72 Edit Distance - Problem Statement
17
LeetCode 72 Edit Distance - Operations
18
LeetCode 72 Edit Distance - State Design
19
LeetCode 72 Edit Distance - Transition
20
LeetCode 72 Edit Distance - Implementation
21
LeetCode 72 Edit Distance - Walkthrough
22
Challenge: Edit Distance Reconstruction
23
Quiz: Edit Distance
24
Lessons from Edit Distance
25
Pattern - String DP
26
LeetCode 516 Longest Palindromic Subsequence - Problem Statement
27
LeetCode 516 Longest Palindromic Subsequence - Walkthrough
28
LeetCode 583 Delete Operation for Two Strings - Problem Statement
29
LeetCode 115 Distinct Subsequences - Problem Statement
30
LeetCode 115 Distinct Subsequences - Walkthrough
31
Quiz: String DP Patterns
32
LeetCode 1092 Shortest Common Supersequence - Problem Statement
33
LeetCode 1092 Shortest Common Supersequence - The LCS Connection
34
LeetCode 1092 Shortest Common Supersequence - Implementation
35
LeetCode 1092 Shortest Common Supersequence - Walkthrough
36
LeetCode 44 Wildcard Matching - Problem Statement
37
LeetCode 44 Wildcard Matching - State Design
38
LeetCode 44 Wildcard Matching - Implementation
39
LeetCode 44 Wildcard Matching - Walkthrough
40
What's Next
41
Section Recap
Interval DP
0/45
1
Intro
2
Core Concept
3
Vocabulary - Interval
4
The Split Point Approach
5
Loop Order
6
Quiz: Interval DP Basics
7
LeetCode 516 Longest Palindromic Subsequence - Problem Statement
8
LeetCode 516 Longest Palindromic Subsequence - Key Observation
9
LeetCode 516 Longest Palindromic Subsequence - State Design
10
LeetCode 516 Longest Palindromic Subsequence - Transition
11
LeetCode 516 Longest Palindromic Subsequence - Implementation
12
LeetCode 516 Longest Palindromic Subsequence - Walkthrough
13
Quiz: LPS Transition
14
Lessons from LPS
15
Matrix Chain Multiplication - Problem Statement
16
Matrix Chain Multiplication - The Setup
17
Matrix Chain Multiplication - State Definition
18
Matrix Chain Multiplication - Transition
19
Matrix Chain Multiplication - Implementation
20
Matrix Chain Multiplication - Walkthrough
21
Challenge: Matrix Chain Reconstruction
22
Quiz: Matrix Chain Complexity
23
Lessons from Matrix Chain
24
LeetCode 312 Burst Balloons - Problem Statement
25
LeetCode 312 Burst Balloons - The Trick
26
LeetCode 312 Burst Balloons - State Definition
27
LeetCode 312 Burst Balloons - Transition
28
LeetCode 312 Burst Balloons - Implementation
29
LeetCode 312 Burst Balloons - Walkthrough
30
Quiz: Burst Balloons Insight
31
Lessons from Burst Balloons
32
LeetCode 132 Palindrome Partitioning II - Problem Statement
33
LeetCode 132 Palindrome Partitioning II - Two DPs
34
LeetCode 132 Palindrome Partitioning II - Implementation
35
LeetCode 132 Palindrome Partitioning II - Walkthrough
36
Challenge: Palindrome Partitioning All
37
Pattern - Interval DP
38
LeetCode 877 Stone Game - Problem Statement
39
LeetCode 877 Stone Game - Implementation
40
Quiz: Stone Game Insight
41
LeetCode 1039 Minimum Score Triangulation of Polygon - Problem Statement
42
LeetCode 1039 Minimum Score Triangulation of Polygon - Implementation
43
Pattern - When Interval DP
44
What's Next
45
Section Recap
DP on Trees
0/43
1
Intro
2
Vocabulary - Subtree
3
The Tree DP Pattern
4
Why Post-Order?
5
Quiz: Tree DP Basics
6
Tree Diameter - Problem Statement
7
Tree Diameter - Key Observation
8
Tree Diameter - State Design
9
Tree Diameter - Implementation
10
Tree Diameter - Walkthrough
11
Challenge: Finding the Actual Path
12
Quiz: Tree Diameter
13
LeetCode 337 House Robber III - Problem Statement
14
LeetCode 337 House Robber III - Key Observation
15
LeetCode 337 House Robber III - State Design
16
LeetCode 337 House Robber III - Implementation
17
LeetCode 337 House Robber III - Walkthrough
18
Challenge: Three States
19
Quiz: House Robber III
20
Rerooting Technique
21
LeetCode 834 Sum of Distances in Tree - Problem Statement
22
LeetCode 834 Sum of Distances in Tree - Key Observation
23
LeetCode 834 Sum of Distances in Tree - Two Passes
24
LeetCode 834 Sum of Distances in Tree - Implementation
25
LeetCode 834 Sum of Distances in Tree - Walkthrough
26
Quiz: Rerooting Complexity
27
LeetCode 124 Binary Tree Maximum Path Sum - Problem Statement
28
LeetCode 124 Binary Tree Maximum Path Sum - Implementation
29
Quiz: Maximum Path Sum
30
LeetCode 310 Minimum Height Trees - Problem Statement
31
LeetCode 310 Minimum Height Trees - Implementation
32
LeetCode 1448 Count Good Nodes in Binary Tree - Problem Statement
33
LeetCode 1448 Count Good Nodes in Binary Tree - Implementation
34
Quiz: Top-Down vs Bottom-Up
35
LeetCode 968 Binary Tree Cameras - Problem Statement
36
LeetCode 968 Binary Tree Cameras - State Transitions
37
LeetCode 968 Binary Tree Cameras - Implementation
38
Quiz: Tree Cameras Intuition
39
Pattern - Tree DP State Design
40
Challenge: DP on DAGs
41
Challenge: Tree DP with Queries
42
What's Next
43
Section Recap
Bitmask DP
0/42
1
Intro
2
Vocabulary - Bitmask
3
Bit Operations
4
Simple Example - Subset Membership
5
Iterating Subsets
6
Quiz: Bit Operations
7
The Bitmask DP Pattern
8
When Bitmask DP?
9
Quiz: When Bitmask DP
10
Subset Sum - Problem Statement
11
Subset Sum - Key Observation
12
Subset Sum - Implementation
13
Quiz: Subset Sum
14
LeetCode 1879 Minimum XOR Sum of Two Arrays - Problem Statement
15
Assignment - key observation
16
Assignment - State Design
17
Assignment - Implementation
18
Quiz: Assignment
19
Hamiltonian Flights - Problem Statement
20
TSP - key observation
21
TSP - State Design
22
TSP - Transition
23
TSP - Implementation
24
Quiz: TSP
25
LeetCode 698 Partition to K Equal Sum Subsets - Problem Statement
26
K Subsets - key observation
27
K Subsets - Implementation
28
Why Sum Over Subsets?
29
Iterating Submasks
30
SOS DP - The Core Idea
31
SOS DP - Transition
32
Quiz: SOS DP Transition
33
SOS DP - Space Optimization
34
SOS DP - Implementation
35
Bit Problem - Problem Statement
36
Bit Problem - Query Analysis
37
Bit Problem - Implementation
38
SOS DP - Superset Version
39
Quiz: SOS DP Applications
40
When to Use SOS DP
41
Lessons from Bitmask DP
42
Section Recap
Digit DP
0/42
1
Intro
2
Core Concept
3
Vocabulary - Tight Bound
4
Quiz: Tight Bound
5
Vocabulary - Leading Zeros
6
Quiz: Leading Zeros
7
The General Pattern
8
Range Queries
9
LeetCode 902 Numbers At Most N Given Digit Set - Problem Statement
10
Digit Set - The Setup
11
Digit Set - State Definition
12
Digit Set - Transition
13
Digit Set - Implementation
14
Digit Set - Walkthrough
15
Lessons from Digit Set
16
Challenge: Digit Set Edge Cases
17
LeetCode 2376 Count Special Integers - Problem Statement
18
Special Integers - The Setup
19
Special Integers - State Definition
20
Special Integers - Transition
21
Special Integers - Implementation
22
Special Integers - Walkthrough
23
Lessons from Special Integers
24
Quiz: Bitmask in Digit DP
25
LeetCode 600 Non-negative Integers without Consecutive Ones - Problem Statement
26
Consecutive Ones - The Setup
27
Consecutive Ones - State Definition
28
Consecutive Ones - Transition
29
Consecutive Ones - Implementation
30
Consecutive Ones - Walkthrough
31
Lessons from Consecutive Ones
32
Challenge: K Consecutive Ones
33
Pattern - Digit DP
34
Digit Sum - Problem Statement
35
Digit Sum - Implementation
36
Quiz: Digit DP Complexity
37
Count Stepping Numbers - Problem Statement
38
Stepping Numbers - Implementation
39
Challenge: Digit DP on Multiple Numbers
40
Pattern - When to Use Digit DP
41
What's Next
42
Section Recap
Game Theory DP
0/46
1
Intro
2
Vocabulary - Optimal Play
3
Winning and Losing States
4
Quiz: Winning vs Losing
5
The Minimax Principle
6
Quiz: Minimax Basics
7
LeetCode 486 Predict the Winner - Problem Statement
8
LeetCode 486 Predict the Winner - Key Idea
9
LeetCode 486 Predict the Winner - State Design
10
LeetCode 486 Predict the Winner - Transition
11
LeetCode 486 Predict the Winner - Implementation
12
LeetCode 486 Predict the Winner - Walkthrough
13
Challenge: First Player Advantage
14
Quiz: Predict the Winner
15
LeetCode 1140 Stone Game II - Problem Statement
16
LeetCode 1140 Stone Game II - Key Idea
17
LeetCode 1140 Stone Game II - State Design
18
LeetCode 1140 Stone Game II - Implementation
19
LeetCode 1140 Stone Game II - Walkthrough
20
Challenge: Stone Game Variants
21
Quiz: Stone Game II
22
LeetCode 464 Can I Win - Problem Statement
23
LeetCode 464 Can I Win - Key Idea
24
LeetCode 464 Can I Win - State Design
25
LeetCode 464 Can I Win - Implementation
26
LeetCode 464 Can I Win - Walkthrough
27
Quiz: Can I Win State
28
Quiz: Can I Win
29
Lessons from Game Theory DP
30
Nim Game - Problem Statement
31
Nim Game - Mathematical Insight
32
Divisor Game - Problem Statement
33
Quiz: Divisor Game Pattern
34
Stone Game IV - Problem Statement
35
Stone Game IV - Implementation
36
Flip Game II - Problem Statement
37
Sprague-Grundy Introduction
38
Quiz: Sprague-Grundy Basics
39
Cat and Mouse - Problem Statement
40
Cat and Mouse - Implementation
41
Quiz: Game with Draws
42
Pattern - Game Theory DP
43
Challenge: Non-Zero-Sum Games
44
Challenge: More Than Two Players
45
What's Next
46
Section Recap
Probability DP
0/44
1
Intro
2
Core Concept
3
Vocabulary - Expected Value
4
Quiz: Expected Value
5
Vocabulary - Transition Probability
6
The Key Formula
7
Quiz: Linearity of Expectation
8
LeetCode 688 Knight Probability in Chessboard - Problem Statement
9
Knight Probability - The Setup
10
Knight Probability - State Definition
11
Knight Probability - Transition
12
Knight Probability - Base Cases
13
Knight Probability - Implementation
14
Knight Probability - Walkthrough
15
Lessons from Knight Probability
16
Challenge: Knight Expected Moves
17
LeetCode 576 Out of Boundary Paths - Problem Statement
18
Out of Boundary - State Definition
19
Out of Boundary - Transition
20
Out of Boundary - Implementation
21
Out of Boundary - Walkthrough
22
Lessons from Out of Boundary
23
Quiz: Out of Boundary Counting
24
LeetCode 808 Soup Servings - Problem Statement
25
LeetCode 808 Soup Servings - The Observation
26
LeetCode 808 Soup Servings - State Definition
27
LeetCode 808 Soup Servings - Transition
28
LeetCode 808 Soup Servings - Implementation
29
LeetCode 808 Soup Servings - Walkthrough
30
Lessons from Soup Servings
31
Quiz: Soup Approximation
32
Pattern - Probability DP
33
LeetCode 837 New 21 Game - Problem Statement
34
LeetCode 837 New 21 Game - Implementation
35
Quiz: New 21 Game Stopping
36
Random Point in Circle - Problem Statement
37
Toss Strange Coins - Problem Statement
38
Toss Strange Coins - Implementation
39
Dice Roll Simulation - Problem Statement
40
Quiz: Dice Roll States
41
Challenge: Infinite Expected Value
42
Pattern - When to Use Probability DP
43
What's Next
44
Section Recap
D&C and Knuth Optimization
0/47
1
Intro
2
When Naive DP Fails
3
Vocabulary - Quadrangle Inequality
4
Quiz: Quadrangle Inequality
5
Why QI Implies Monotonicity
6
Quiz: Monotonicity Implication
7
D&C and Knuth Overview
8
What Is D&C Optimization?
9
The D&C Recursion
10
D&C Recursion - Walkthrough
11
Why D&C Is O(n log n)
12
Quiz: D&C Complexity
13
Visualizing D&C
14
Codeforces 321E Ciel and Gondola - Problem Statement
15
Codeforces 321E Ciel and Gondola - The DP
16
Codeforces 321E Ciel and Gondola - Why QI Holds
17
Codeforces 321E Ciel and Gondola - Implementation
18
Codeforces 321E Ciel and Gondola - Walkthrough
19
Lessons from D&C Optimization
20
Challenge: Proving QI
21
What Is Knuth's Optimization?
22
The Double Bound
23
The Iteration Order
24
Knuth's Optimization - Walkthrough
25
Why O(n²) Total
26
Visualizing Knuth
27
Optimal BST - Problem Statement
28
Optimal BST - The DP
29
Optimal BST - Why QI Holds
30
Optimal BST - Implementation
31
Optimal BST - Walkthrough
32
Lessons from Knuth's Optimization
33
Breaking a String - Problem Statement
34
Breaking a String - Implementation
35
Printing Neatly - Problem Statement
36
Server Allocation - Problem Statement
37
Server Allocation - Implementation
38
D&C vs Knuth
39
Quiz: Knuth vs D&C
40
Common Mistakes
41
Challenge: When QI Fails
42
Challenge: Combining with Other Techniques
43
Pattern - Quadrangle Optimizations
44
Implementation Checklist
45
Practice - Identify the Optimization
46
What's Next
47
Section Recap
Convex Hull Trick
0/43
1
Intro
2
A Different Pattern
3
Vocabulary - Linear Function
4
Rewriting the DP
5
Quiz: Linear Form Recognition
6
The Key Observation
7
Vocabulary - Lower Envelope
8
Quiz: Lower Envelope
9
Why Most Lines Don't Matter
10
What Is the Convex Hull Trick?
11
When Queries Are Sorted
12
The Deque Approach
13
Deque Operations - Walkthrough
14
Adding a New Line
15
Quiz: Deque Invariant
16
Querying the Minimum
17
CHT Query - Walkthrough
18
Why O(n) Total
19
Visualizing CHT
20
Codeforces 319C Kalila and Dimna - Problem Statement
21
Codeforces 319C Kalila and Dimna - The DP
22
Codeforces 319C Kalila and Dimna - CHT Form
23
Codeforces 319C Kalila and Dimna - Why It Works
24
Codeforces 319C Kalila and Dimna - Implementation
25
Codeforces 319C Kalila and Dimna - Walkthrough
26
Lessons from CHT
27
Challenge: Non-Sorted Slopes
28
When Queries Aren't Sorted
29
Binary Search on the Hull
30
Vocabulary - Li Chao Tree
31
Li Chao Tree - Walkthrough
32
Quiz: Li Chao vs Deque
33
Common Mistakes
34
Commando - Problem Statement
35
Commando - Implementation
36
Covered Walkway - Problem Statement
37
Quiz: Covered Walkway Algebra
38
Challenge: 2D CHT
39
Pattern - Convex Hull Trick
40
Pattern - CHT Recognition
41
Implementation Tips
42
What's Next
43
Section Recap
Monotonic Queue Optimization
0/45
1
Intro
2
The Problem
3
Vocabulary - Monotonic Queue
4
Quiz: Why Monotonic
5
The Core Idea
6
Monotonic Queue - How It Works
7
Monotonic Queue - Walkthrough
8
Quiz: Monotonic Queue
9
LeetCode 239 Sliding Window Maximum - Problem Statement
10
Sliding Maximum - The Approach
11
Sliding Maximum - The Pattern
12
Sliding Maximum - Implementation
13
Sliding Maximum - Walkthrough
14
LeetCode 1696 Jump Game VI - Problem Statement
15
LeetCode 1696 Jump Game VI - DP Formulation
16
LeetCode 1696 Jump Game VI - Optimization
17
LeetCode 1696 Jump Game VI - Implementation
18
LeetCode 1696 Jump Game VI - Walkthrough
19
Quiz: Jump Game VI
20
Challenge: Variable Window Size
21
LeetCode 1425 Constrained Subsequence Sum - Problem Statement
22
Constrained Sum - DP Formulation
23
Constrained Sum - Implementation
24
Constrained Sum - Walkthrough
25
LeetCode 862 Shortest Subarray with Sum at Least K - Problem Statement
26
Shortest Subarray - Prefix Sums
27
Shortest Subarray - The Idea
28
Shortest Subarray - Implementation
29
Shortest Subarray - Walkthrough
30
Quiz: Shortest Subarray
31
Challenge: Negative Values
32
When to Use Monotonic Queue
33
Max Sum of Rectangle - Problem Statement
34
Max Consecutive Ones III - Problem Statement
35
Quiz: When Monotonic Queue
36
Increasing vs Decreasing
37
Increasing vs Decreasing - Walkthrough
38
Longest Continuous Subarray - Problem Statement
39
Longest Subarray - Implementation
40
Challenge: Online vs Offline
41
Monotonic Queue vs Other Techniques
42
Pattern - Monotonic Queue Recognition
43
Implementation Template
44
What's Next
45
Section Recap
Aliens Trick (WQS Binary Search)
0/41
1
Intro
2
The Problem
3
The Insight
4
Quiz: Penalty Intuition
5
From Two Dimensions to One
6
Binary Search on Lambda
7
Binary Search - Walkthrough
8
Why It Works
9
Quiz: Convexity Requirement
10
Tracking the Count
11
Tracking Count - Walkthrough
12
Quiz: Aliens Trick Basics
13
Building a Tall Barn - Problem Statement
14
Tall Barn - Convexity
15
Tall Barn - Penalized DP
16
Tall Barn - Implementation
17
Tall Barn - Walkthrough
18
Codeforces 674C Levels and Regions - Problem Statement
19
Codeforces 674C Levels and Regions - Standard DP
20
Codeforces 674C Levels and Regions - Aliens Trick
21
Codeforces 674C Levels and Regions - CHT Combination
22
Codeforces 674C Levels and Regions - Walkthrough
23
Codeforces 739E Gosha is Hunting - Problem Statement
24
Gosha - Nested Binary Search
25
Gosha - Implementation
26
Gosha - Walkthrough
27
Quiz: Two-Dimensional Aliens
28
Quiz: Nested Binary Search
29
IOI 2016 Aliens - Problem Statement
30
IOI Aliens - Preprocessing
31
IOI Aliens - DP Formulation
32
IOI Aliens - Combined Optimization
33
IOI Aliens - Implementation
34
IOI Aliens - Walkthrough
35
When to Use Aliens Trick
36
Challenge: When Convexity Fails
37
Common Mistakes
38
Implementation Checklist
39
Pattern - Aliens Recognition
40
What's Next
41
Section Recap
Slope Trick
0/47
1
Intro
2
Piecewise Linear Functions
3
Quiz: Piecewise Linear
4
Vocabulary - Slope-Change Points
5
Heap Representation
6
Heap Representation - Walkthrough
7
Quiz: Slope-Change Points
8
Quiz: Why Two Heaps
9
Codeforces 713C Sonya and Problem Without a Legend - Problem Statement
10
Sonya - Transform Trick
11
Sonya - DP Formulation
12
Sonya - Heap Operations
13
Sonya - Implementation
14
Sonya - Walkthrough
15
Challenge: Strictly Increasing
16
Codeforces 865D Buy Low Sell High - Problem Statement
17
Codeforces 865D Buy Low Sell High - The Idea
18
Codeforces 865D Buy Low Sell High - Why It Works
19
Codeforces 865D Buy Low Sell High - Implementation
20
Codeforces 865D Buy Low Sell High - Walkthrough
21
Quiz: Regret Trick
22
CSES Increasing Array II - Problem Statement
23
CSES - DP Function Shape
24
CSES - Heap Mechanics
25
CSES - Implementation
26
CSES - Walkthrough
27
Prefix Min Operation
28
Prefix Min Operation - Walkthrough
29
K-Increasing - Problem Statement
30
Jobs and Deadlines - Problem Statement
31
When to Use Slope Trick
32
Quiz: When Slope Trick
33
Common Mistakes
34
Common Mistakes - Walkthrough
35
Complexity Analysis
36
Complexity Analysis - Walkthrough
37
Making Array Beautiful - Problem Statement
38
Challenge: Three Heaps
39
Lazy Propagation
40
Potions - Problem Statement
41
Quiz: Slope Trick vs CHT
42
Practice Strategy
43
Pattern - Slope Trick Recognition
44
Implementation Template
45
Challenge: Online Queries
46
What's Next
47
Section Recap
Broken Profile DP (Plug DP)
0/42
1
Intro
2
The Profile Concept
3
Quiz: Profile Concept
4
Why Bitmasks Work
5
Bitmask Encoding - Walkthrough
6
State Transitions
7
State Transitions - Walkthrough
8
Quiz: Profile Encoding
9
Counting Tilings - Problem Statement
10
Counting Tilings - State Definition
11
Counting Tilings - Filling a Column
12
Counting Tilings - Transition Formula
13
Counting Tilings - Implementation
14
Counting Tilings - Walkthrough
15
Challenge: Transition Enumeration
16
Quiz: Transition Count
17
Tri Tiling - Problem Statement
18
Tri Tiling - Small Cases
19
Tri Tiling - Recurrence Discovery
20
Tri Tiling - Implementation
21
Tri Tiling - Walkthrough
22
When Width Is Fixed
23
Quiz: Why Small Width
24
LeetCode 790 Domino and Tromino Tiling - Problem Statement
25
Domino and Tromino - Profile States
26
Domino and Tromino - Transitions
27
Domino and Tromino - Simplified Recurrence
28
Simplified Recurrence - Walkthrough
29
Domino and Tromino - Implementation
30
Domino and Tromino - Walkthrough
31
Quiz: Profile Count
32
Chessboard Coloring - Problem Statement
33
Hamiltonian Paths - Problem Statement
34
Challenge: Larger Tiles
35
When to Use Broken Profile DP
36
Pattern - Broken Profile Recognition
37
Course Conclusion
38
Complexity Analysis
39
Complexity Analysis - Walkthrough
40
Common Mistakes
41
Common Mistakes - Walkthrough
42
Section Recap
Dynamic Programming - Roadmaps | Repovive