Dynamic Programming

Dynamic Programming (DP) is a powerful technique for solving optimization problems by breaking them down into simpler subproblems and storing solutions to avoid redundant calculations.

Learning Map

Dynamic programming concepts and problem types organized by complexity.

Prerequisites

• Time & Space Complexity Analysis
• Arrays & Strings
• Hash Tables & Sets
• Trees & Binary Trees

What's in scope

• DP Fundamentals: Core concepts including overlapping subproblems, optimal substructure, and implementation approaches
• Classic DP Problems: Essential problems like Fibonacci, climbing stairs, house robber, and coin change
• Advanced DP Patterns: Complex patterns including knapsack, edit distance, and matrix chain multiplication
• DP on Trees & Graphs: Applying dynamic programming to tree and graph structures

How to use this section

• Start with DP Fundamentals to understand the core concepts
• Practice Classic DP Problems to build intuition
• Master Advanced DP Patterns for complex problems
• Explore DP on Trees & Graphs for specialized applications

📄️ DP Fundamentals

Understand overlapping subproblems, optimal substructure, memoization vs tabulation, and the core principles of dynamic programming.

📄️ Classic DP Problems

Master fundamental dynamic programming problems including 0/1 Knapsack, Longest Common Subsequence, Longest Increasing Subsequence, Coin Change, and Edit Distance.

📄️ Advanced DP Patterns

Master advanced dynamic programming techniques including interval DP, bitmask DP, digit DP, and DP optimizations with Knuth-Yao and divide-and-conquer.

📄️ DP on Trees and Graphs

Apply dynamic programming to tree and graph problems including tree DP, rerooting technique, DAG DP, and shortest paths as DP.