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

Dynamic Programming Fundamentals

1000 → 1700

1300 → 1700

You know recursion. Now see how memoization and tabulation turn exponential solutions into polynomial ones.

Intro

The power of optimization

LeetCode 509 Fibonacci - Problem Statement

LC 509 classic

LeetCode 509 Fibonacci - Base Cases

Two starting points

LeetCode 509 Fibonacci - Recursive Formula

Two calls

LeetCode 509 Fibonacci - Naive Implementation

Direct translation

Visualization - Fibonacci Tree

Explosion of calls

Vocabulary - Overlapping Subproblems

Same work repeated

Time Complexity - Exponential Growth

O(2^n) disaster

The Main Idea

Remember results

Socratic Checkpoint

Test your understanding

Recursion to DP

The bridge

What Is Memoization?

Caching results

Vocabulary - Top-Down DP

Starting from the top

LeetCode 509 Fibonacci - Memoization Setup

Adding memory

LeetCode 509 Fibonacci - Memoized Code

Three extra lines

Memoization - Time Complexity

O(n) now!

Memoization - Space Complexity

O(n) cost

LeetCode 70 Climbing Stairs - Problem Statement

LC 70 Fibonacci disguise

LeetCode 70 Climbing Stairs - Recursive Intuition

DP basics

LeetCode 70 Climbing Stairs - Memoized Solution

Apply the pattern

LeetCode 70 Climbing Stairs - Implementation

The code

Quiz: Memoization Complexity

Knowledge check

Lessons from Memoization

Pattern recap

What Is Tabulation?

Building from ground up

Vocabulary - Bottom-Up DP

Why called bottom-up

LeetCode 509 Fibonacci - Tabulation Implementation

Iterative solution

Space Optimization

Only keep what you need

LeetCode 509 Fibonacci - O(1) Space

Most efficient

Top-Down vs Bottom-Up

When to use each

LeetCode 746 Min Cost Climbing Stairs - Problem Statement

Your first cost problem

LeetCode 746 Min Cost Climbing Stairs - State Definition

What dp[i] means

LeetCode 746 Min Cost Climbing Stairs - Transition

Choose cheaper path

LeetCode 746 Min Cost Climbing Stairs - Implementation

Full solution

LeetCode 152 Maximum Product Subarray - Problem Statement

Read the problem

LeetCode 152 Maximum Product Subarray - Why It's Tricky

Negative numbers twist

LeetCode 152 Maximum Product Subarray - Tracking Two States

Track min and max

LeetCode 152 Maximum Product Subarray - Implementation

Full solution

Quiz: Simple DP Patterns

Knowledge check

LeetCode 91 Decode Ways - Problem Statement

LeetCode 91

LeetCode 91 Decode Ways - The Choices

One or two digits

LeetCode 91 Decode Ways - Edge Cases

Leading zeros

LeetCode 91 Decode Ways - State Definition

Ways to decode

LeetCode 91 Decode Ways - Transition

Two choices

LeetCode 91 Decode Ways - Implementation

The code

Section Recap

What we learned

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

$ curl repovive.com/roadmaps/dynamic-programming

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