Loading repovive.com/roadmaps/dp-problem-solving
Roadmaps
Dynamic Programming: Problem Solving
Premium
Problemset
Discussion
AI Helper
Getting Started
0/4
1
Intro
2
Who This Is For
3
What You'll Learn
4
How to Use This Roadmap
Knapsack
0/56
1
Introduction to Knapsack
2
What Knapsack DP Solves
3
When to Use Knapsack DP
4
Problem - Tallest Billboard
5
Tallest Billboard - Why Naive Fails
6
Tallest Billboard - Defining the DP
7
Tallest Billboard - Transition
8
Tallest Billboard - Base Cases
9
Tallest Billboard - Implementation
10
Tallest Billboard - Time and Space
11
Lessons from Tallest Billboard
12
Problem - Values You Can Make
13
Values You Can Make - Why Naive Fails
14
Values You Can Make - Defining the DP
15
Values You Can Make - Transition
16
Values You Can Make - Base Cases
17
Values You Can Make - Implementation
18
Values You Can Make - Time and Space
19
Lessons from Values You Can Make
20
Problem - Profitable Schemes
21
Profitable Schemes - Why Naive Fails
22
Profitable Schemes - Defining the DP
23
Profitable Schemes - Core Logic
24
Profitable Schemes - Implementation
25
Lessons from Profitable Schemes
26
Problem - Round Subset
27
Round Subset - Why Naive Fails
28
Round Subset - Defining the DP
29
Round Subset - Core Logic
30
Round Subset - Implementation
31
Lessons from Round Subset
32
Problem - Fire
33
Fire - Why Naive Fails
34
Fire - Defining the DP
35
Fire - Core Logic
36
Fire - Implementation
37
Lessons from Fire
38
Space Optimization - Why It Works
39
Space Optimization - Implementation
40
Bounded Knapsack - Problem Pattern
41
Reconstruction - Finding Selected Items
42
Reconstruction - Code Pattern
43
Quiz: Pattern Recognition
44
Quiz: Edge Cases
45
Common Mistakes in Knapsack DP
46
Problem - Number of Ways to Earn Points
47
Number of Ways to Earn Points - Implementation
48
Problem - Two Sets II
49
Two Sets II - Implementation
50
Problem - Painting the Walls
51
Painting the Walls - Implementation
52
Problem - Number of Great Partitions
53
Number of Great Partitions - Implementation
54
Problem - Meet in the Middle
55
Meet in the Middle - Implementation
56
Section Recap
Interval DP
0/38
1
What Interval DP Solves
2
When to Use Interval DP
3
Problem - Zuma
4
Zuma - Why Naive Fails
5
Zuma - Defining the DP
6
Zuma - Transition
7
Zuma - Base Cases
8
Zuma - Implementation
9
Zuma - Time and Space
10
Problem - Merge Stones
11
Merge Stones - Feasibility Check
12
Merge Stones - Defining the DP
13
Merge Stones - Core Logic
14
Merge Stones - Implementation
15
Problem - Coloring Brackets
16
Coloring Brackets - Why Naive Fails
17
Coloring Brackets - Defining the DP
18
Coloring Brackets - Core Logic
19
Coloring Brackets - Implementation
20
Problem - Polygon Triangulation
21
Polygon Triangulation - Why Naive Fails
22
Polygon Triangulation - Defining the DP
23
Polygon Triangulation - Core Logic
24
Polygon Triangulation - Implementation
25
Problem - Minimum Cost to Cut Stick
26
Minimum Cost to Cut Stick - Solution
27
Problem - Strange Printer
28
Strange Printer - Solution
29
Problem - Remove Boxes
30
Remove Boxes - Solution
31
Quiz: Interval DP Patterns
32
Quiz: Interval DP Edge Cases
33
Common Mistakes in Interval DP
34
Problem - Encode String with Shortest Length
35
Encode String with Shortest Length - Implementation
36
Problem - Palindrome Removal
37
Palindrome Removal - Implementation
38
Section Recap
DP on Trees
0/44
1
Introduction to DP on Trees
2
What Tree DP Solves
3
When to Use Tree DP
4
Problem - Binary Tree Max Path Sum
5
Binary Tree Max Path Sum - Why Naive Fails
6
Binary Tree Max Path Sum - Defining the DP
7
Binary Tree Max Path Sum - Transition
8
Binary Tree Max Path Sum - Base Cases
9
Binary Tree Max Path Sum - Implementation
10
Binary Tree Max Path Sum - Time and Space
11
Binary Tree Max Path Sum - Edge Cases
12
Lessons from Binary Tree Max Path Sum
13
Problem - Tree Distances II
14
Tree Distances II - Why Naive Fails
15
Tree Distances II - Defining the DP
16
Tree Distances II - Transition
17
Tree Distances II - Base Cases
18
Tree Distances II - Implementation
19
Tree Distances II - Time and Space
20
Tree Distances II - Edge Cases
21
Lessons from Tree Distances II
22
Problem - Distance in Tree
23
Distance in Tree - Why Naive Fails
24
Distance in Tree - Defining the DP
25
Distance in Tree - Core Logic
26
Distance in Tree - Implementation
27
Lessons from Distance in Tree
28
Problem - Tree Diameter
29
Tree Diameter - Solution
30
Tree Diameter - Complexity
31
Problem - Tree Painting
32
Tree Painting - Solution
33
Tree Painting - Rerooting Formula
34
Problem - Tree Matching
35
Tree Matching - Solution
36
Tree Matching - Greedy Solution
37
Problem - Binary Tree Cameras
38
Binary Tree Cameras - Solution
39
Quiz: Tree DP Patterns
40
Quiz: Tree DP Edge Cases
41
Common Mistakes in Tree DP
42
Problem - Longest Path With Different Adjacent Characters
43
Longest Path With Different Adjacent Characters - Implementation
44
Section Recap
Bitmask DP
0/50
1
Introduction to Bitmask DP
2
What Bitmask DP Solves
3
When to Use Bitmask DP
4
Problem - TSP
5
TSP - Why Naive Fails
6
TSP - Defining the DP
7
TSP - Transition
8
TSP - Base Cases
9
TSP - Implementation
10
TSP - Time and Space
11
TSP - Edge Cases
12
Lessons from TSP
13
Problem - Shortest Hamiltonian Path
14
Shortest Hamiltonian Path - Solution
15
Lessons from Shortest Hamiltonian Path
16
Assignment Problem - Overview
17
Assignment Problem - Why Naive Fails
18
Assignment Problem - Defining the DP
19
Assignment Problem - Core Logic
20
Assignment Problem - Implementation
21
Lessons from Assignment Problem
22
Shortest Superstring - Overview
23
Shortest Superstring - Why Naive Fails
24
Shortest Superstring - Defining the DP
25
Shortest Superstring - Core Logic
26
Shortest Superstring - Implementation
27
Lessons from Shortest Superstring
28
Sum over Subsets (SOS) DP - Problem Pattern
29
SOS DP - Why Naive Fails
30
SOS DP - Space-Optimized Implementation
31
SOS DP - Applications
32
Problem - Elevator Problem
33
Elevator Problem - Solution
34
Elevator Problem - State Transition
35
Iterating Over Submasks - Technique
36
Iterating Over Submasks - When to Use
37
Problem - Special Permutations
38
Special Permutations - Solution
39
Problem - Maximize Score
40
Maximize Score - Solution
41
Problem - Beautiful Arrangement
42
Beautiful Arrangement - Solution
43
Quiz: Bitmask DP Patterns
44
Quiz: Bitmask Edge Cases
45
Common Mistakes in Bitmask DP
46
Problem - Maximum Students Taking Exam
47
Maximum Students Taking Exam - Implementation
48
Problem - Number of Ways to Wear Different Hats
49
Number of Ways to Wear Different Hats - Implementation
50
Section Recap
String DP
0/38
1
Introduction to String DP
2
When to Use String DP
3
Problem - Regex Matching
4
Regex Matching - Why Naive Fails
5
Regex Matching - Defining the DP
6
Regex Matching - Transition
7
Regex Matching - Base Cases
8
Regex Matching - Implementation
9
Regex Matching - Time and Space
10
Regex Matching - Edge Cases
11
Lessons from Regex Matching
12
Problem - Interleaving String
13
Interleaving String - Why DP?
14
Interleaving String - Solution
15
Interleaving String - Building the State
16
Problem - Palindrome Partitioning
17
Palindrome Partitioning - Solution
18
Palindrome Partitioning - Precomputation
19
SCS - Solution
20
SCS - Reconstruction
21
Problem - Longest Palindromic Substring
22
Longest Palindromic Substring - Solution
23
Problem - Word Break
24
Word Break - Solution
25
Quiz: String DP Patterns
26
Quiz: String DP Edge Cases
27
Common Mistakes in String DP
28
Problem - Scramble String
29
Scramble String - Implementation
30
Problem - Count Different Palindromic Subsequences
31
Count Different Palindromic Subsequences - Implementation
32
Problem - Distinct Subsequences II
33
Distinct Subsequences II - Implementation
34
Problem - Palindrome Partitioning III
35
Palindrome Partitioning III - Implementation
36
Problem - Number of Ways to Form Target String
37
Number of Ways to Form Target String - Implementation
38
Section Recap
Game Theory DP
0/44
1
Introduction to Game Theory DP
2
When to Use Game Theory DP
3
Problem - Stone Game IV
4
Stone Game IV - Why Naive Fails
5
Stone Game IV - Defining the DP
6
Stone Game IV - Transition
7
Stone Game IV - Base Cases
8
Stone Game IV - Implementation
9
Stone Game IV - Time and Space
10
Problem - Stone Game III
11
Stone Game III - Why Naive Fails
12
Stone Game III - Defining the DP
13
Stone Game III - Transition
14
Stone Game III - Base Cases
15
Stone Game III - Implementation
16
Stone Game III - Time and Space
17
Nim Game - Overview
18
Nim Game - Why Naive Fails
19
Nim Game - Defining the DP
20
Nim Game - Core Logic
21
Lessons from Nim Game
22
Staircase Nim - Why Odd Steps Matter
23
Staircase Nim - Winning Strategy
24
Staircase Nim - Problem Pattern
25
Staircase Nim - Implementation
26
Composite Games - Sprague-Grundy Theorem
27
Computing Grundy Numbers
28
Game on DAG - Applying Grundy
29
Problem - Stone Game I
30
Stone Game I - Solution
31
Stone Game I - One-Liner
32
Problem - Stone Game VII
33
Stone Game VII - Solution
34
Stone Game VII - Implementation
35
Quiz: Game Theory Patterns
36
Quiz: Game Theory Edge Cases
37
Common Mistakes in Game Theory DP
38
Problem - Cat and Mouse
39
Cat and Mouse - Implementation
40
Problem - Stone Game VIII
41
Stone Game VIII - Implementation
42
Problem - Grundy's Game
43
Grundy's Game - Implementation
44
Section Recap
Digit DP
0/58
1
Introduction to Digit DP Problems
2
Template Overview
3
The Digit DP Template
4
Problem - Counting Numbers
5
Counting Numbers - State Design
6
Counting Numbers - Implementation
7
Counting Numbers - Complexity
8
Lessons from Counting Numbers
9
Problem - Number of Digit One
10
Digit One - Positional Counting
11
Digit One - Implementation
12
Digit One - Time and Space
13
Lessons from Digit One
14
Quiz: Digit DP States
15
Problem - Classy Numbers
16
Classy Numbers - State Design
17
Classy Numbers - Transition
18
Classy Numbers - Implementation
19
Lessons from Classy Numbers
20
Problem - Roman and Numbers
21
Roman and Numbers - Why Naive Fails
22
Roman and Numbers - Bitmask with Remainder
23
Roman and Numbers - Implementation
24
Lessons from Roman and Numbers
25
Quiz: Bitmask in Digit DP
26
Problem - Magic Numbers
27
Magic Numbers - Position-Dependent Rules
28
Magic Numbers - Implementation
29
Magic Numbers - Complexity
30
Magic Numbers - Time and Space
31
Lessons from Magic Numbers
32
Problem - Palindromic Numbers
33
Palindromic Numbers - Half Freedom
34
Palindromic Numbers - Implementation
35
Lessons from Palindromic Numbers
36
Quiz: Palindrome Constraints
37
Problem - Segment Sum
38
Segment Sum - Tracking Both Count and Sum
39
Segment Sum - Sum Tracking
40
Segment Sum - Implementation
41
Segment Sum - Time and Space
42
Lessons from Segment Sum
43
Problem - Beautiful Numbers
44
Beautiful Numbers - The LCM Trick
45
Beautiful Numbers - LCM Trick
46
Beautiful Numbers - Implementation
47
Beautiful Numbers - Time and Space
48
Lessons from Beautiful Numbers
49
Quiz: Advanced Techniques
50
Problem - Daniel and Spring Cleaning
51
Spring Cleaning - Binary Digit DP
52
Spring Cleaning - Implementation
53
Spring Cleaning - Complexity
54
Lessons from Spring Cleaning
55
Common Mistakes in Digit DP
56
Quiz: Final Assessment
57
What's Next
58
Section Recap