Dynamic Programming

What you'll learn

• The Golden Rules for DP Identification

  Before jumping into categories, master these four questions. If you answer YES to all four, you almost certainly have a DP problem.

• Rule 1: "Can I make a CHOICE at each step?"

  At every stage of the problem, you face a decision: - Include or exclude this item - Take or skip this element - Pick from the left end or the right end - Use this coin or dont use it - Match this character or skip it If the problem forc…

• Rule 2: "Does making that choice leave me with a SMALLER version of the same problem?"

  This is optimal substructure. After making your choice, the remaining problem has the exact same structure, just smaller.

• Rule 3: "Will I solve the same subproblem MULTIPLE times?"

  This is overlapping subproblems. Draw the recursion tree. If you see the same function call appearing in multiple branches, you have overlap. Without memoization, the same computation repeats exponentially.

• Rule 4: "Am I asked for count/optimize/possibility?"

  DP problems almost always ask one of: - Count: "How many ways can you...?" - Optimize: "What is the minimum/maximum...?" - Possibility: "Can you...?" / "Is it possible to...?" If the problem asks you to enumerate all solutions or print a…

• Top-Down (Memoization) vs Bottom-Up (Tabulation)

• Top-Down: Start from the big problem, recurse down

  When to use top-down: - The state space is large but only a fraction is actually visited - The recursive structure is natural and easy to reason about - You want to quickly convert a brute-force recursive solution

• Bottom-Up: Start from smallest subproblems, build up

  When to use bottom-up: - You need every subproblem solved (dense state space) - You want to optimize space (rolling arrays) - You want to avoid recursion stack overflow - Iterative solution is straightforward ---

• The 6-Step DP Problem-Solving Process

  A systematic framework for converting any DP problem into working, optimized code: | Step | Action | Output | |------|--------|--------| | 1. Find Recurrence | Define what dp(i) means clearly; express answer for larger input in terms of…

• State Design Methodology

  The hardest part of DP is defining your state. Ask: "What information do I need to make a decision at the current step?"

• The "Consistency of Definition" Principle

  How you define dp(i) cascades through everything -- base cases, recurrence indexing, loop bounds, and answer location all change if the definition changes. This is the #1 source of off-by-one bugs in DP. Always write out what dp(i) means…

• Step-by-step state design:

  1. Identify what changes between subproblems (index, remaining capacity, last character matched, etc.) 2. Each changing variable becomes a dimension of your DP table 3. Define what the state STORES: the answer to "given these parameters,…

• Example: Knapsack

  - What changes? Current item index, remaining weight capacity - State: dp[i][w] = maximum value using items 0..i with capacity w - Can I compute from previous? Yes: either include item i or skip it

• Common state patterns:

  | Pattern | State variables | |---------|----------------| | Linear sequence | Index i | | Two sequences | Index i in first, index j in second | | Knapsack variants | Index + remaining capacity | | Interval/range | Left endpoint, right e…

• Transition Formula

• How to find the recurrence relation

  Assume you already know the answer for all smaller inputs. For arrays: assume you know dp(0), dp(1), ..., dp(i-1). For strings: assume answers for all shorter prefixes. Then ask: "Can I use these known answers to compute dp(i) for the fu…

• The transition encodes choices

  The transition (recurrence relation) defines how states connect. It encodes the CHOICES you can make. General template: ---

• Category 1: 0/1 Knapsack Family

• Core Idea

  You have items, each used at most once. For each item, you decide: INCLUDE or EXCLUDE.

• Template

  Key insight: When we include item i, we look at dp[i-1][...] (previous row), ensuring each item is used only once.

• Worked Example: Subset Sum

  Problem: Given a set of positive integers, determine if there exists a subset that sums to a target value. State: dp[i][s] = "Can we form sum s using items 0..i-1?" Transition: - Exclude item i: dp[i][s] = dp[i-1][s] - Include item i: dp…

• Equal Partition Problem

  Problem: Can you partition an array into two subsets with equal sum? Reduction: If total sum is odd, impossible. Otherwise, find a subset summing to totalSum / 2. This is exactly subset sum.

• Count of Subsets with Given Sum

  Variation: Instead of boolean (can/cant), count how many subsets sum to target. Change: dp[i][s] = dp[i-1][s] + dp[i-1][s - items[i]] (exclude count + include count) ---

• Category 2: Unbounded Knapsack

• Core Idea

  Items can be used unlimited times. The choice is: how many of each item to use.

• Critical Difference from 0/1

  In 0/1 Knapsack, when including item i, you reference the previous row (dp[i-1][...]). In Unbounded Knapsack, when including item i, you reference the current row (dp[i][...]), allowing the same item to be picked again.

• Space-Optimized 1D version

  For unbounded knapsack with 1D array, iterate capacity left to right (allows reuse): For 0/1 knapsack with 1D array, iterate capacity right to left (prevents reuse):

• Worked Example: Coin Change (Minimum Coins)

  Problem: Given coin denominations and a target amount, find the minimum number of coins needed. State: dp[amount] = minimum coins to make this amount Cleaner trace:

• Rod Cutting

  Problem: Cut a rod of length n to maximize profit. You have prices for each length 1..n. This is unbounded knapsack where "items" are pieces of different lengths, and "capacity" is the rod length. Each piece length can be used multiple t…

• Category 3: Longest Common Subsequence (LCS) Family

• Core Idea

  Compare two sequences character by character. At each position pair (i, j), decide: do these characters match, and what follows from that?

• Template

• Worked Example

  Fill logic: - Characters match: take diagonal + 1 (both characters are part of LCS) - Characters differ: take max of (skip from first, skip from second)

• Longest Common Substring

  Difference from LCS: Characters must be contiguous. If characters dont match, reset to 0 instead of taking max of neighbors.

• Edit Distance (Levenshtein Distance)

  Problem: Minimum operations (insert, delete, replace) to transform one string into another.

• Wildcard / Regex Pattern Matching

  Problem: Given a string and a pattern with special characters (. matches any single character, means zero or more of the preceding element), determine if the pattern matches the entire string. Recursive Insight: 1. If the pattern is emp…

• Shortest Common Supersequence

  Problem: Shortest string that has both strings as subsequences. Key insight: Length = len(s1) + len(s2) - LCS(s1, s2) The LCS characters are shared; everything else must appear once from each string. ---

• Category 4: Longest Increasing Subsequence (LIS)

• Core Idea

  Find the longest subsequence where each element is strictly greater than the previous.

• O(n^2) DP Approach

  State: dp[i] = length of longest increasing subsequence ending at index i. Transition: For each j Intuition: We greedily keep the smallest possible tail for each length. A smaller tail gives us more room to extend later. Note: tails itse…

• Category 5: Matrix Chain / Interval DP

• Core Idea

  Partition a range into two subranges, solve each optimally, and combine. You try EVERY possible split point.

• Template

• The "Gap" Strategy for Filling

  Unlike row-by-row filling, interval DP fills by increasing subproblem size: This ensures when computing dp[i][j], all smaller subranges are already solved.

• Worked Example: Matrix Chain Multiplication

  Problem: Given matrices with dimensions such that matrix i is dims[i] x dims[i+1], find the minimum number of scalar multiplications to compute their product.

• Burst Balloons

  Problem: Given balloons with values, burst them one by one. When you burst balloon i, you get value[left] value[i] value[right]. Maximize total coins. Key insight: Think in reverse. Instead of "which to burst first," think "which to bu…

• Palindrome Partitioning (Minimum Cuts)

  Problem: Minimum cuts to partition a string so every part is a palindrome. State: dp[i][j] = minimum cuts for substring [i..j] Transition: If s[i..j] is a palindrome, dp[i][j] = 0. Otherwise, try every split point. ---

• Category 6: DP on Strings

• Longest Palindromic Subsequence

  Problem: Find the longest subsequence of a string that is a palindrome. Key insight: LPS(s) = LCS(s, reverse(s)) Or directly:

• Longest Palindromic Substring (O(n) — Expand with Sentinel Characters)

  Problem: Find the longest contiguous palindromic substring. Approach 1 — Expand Around Center (O(n^2)): For each of the 2n-1 centers (n char centers + n-1 gap centers), expand outward while characters match. Simple and often good enough.…

• Word Break

  Problem: Can a string be segmented into words from a dictionary? State: dp[i] = "Can s[0..i-1] be segmented?" Transition: Try every possible last word ending at position i. ---

• Category 7: DP on Trees

• Core Idea

  Solve subproblems rooted at subtrees. Each node aggregates results from its children.

• Template

• Maximum Path Sum in Binary Tree

  Problem: Find the path with maximum sum. Path can start and end at any node. Key insight: At each node, you make two computations: 1. Best path passing THROUGH this node (uses both children) - updates global answer 2. Best path going UP…

• House Robber on Tree

  Problem: Like house robber but on a binary tree. Cannot rob adjacent nodes (parent-child). ---

• Space Optimization: Rolling Array

• From 2D to 1D

  Many DP problems only need the previous row to compute the current row. We can reduce O(nm) space to O(m). Before (2 rows needed): After (rolling two rows):

• From 2 Rows to True 1D (Knapsack style)

  For 0/1 knapsack, iterate right-to-left to simulate having the previous row: Right-to-left ensures dp[w - item.weight] still holds the "previous row" value (hasnt been updated yet in this pass). ---

• Solution Traceback

  Often you need the actual solution, not just the optimal value.

• Strategy 1: Store choices during DP fill

• Strategy 2: Reconstruct from DP table values

  For LCS, trace back by checking which direction the value came from: ---

• Category 8: Fibonacci / Linear DP

• Core Idea

  Each state depends on a fixed number of immediately preceding states. The simplest form: dp[i] = f(dp[i-1], dp[i-2], ...).

• Template

  Space: O(1) since only the last k states are needed.

• Worked Example: Climbing Stairs

  Problem: You can climb 1 or 2 steps at a time. How many distinct ways to reach step n? This IS the Fibonacci sequence. The number of ways to reach step n = Fib(n+1).

• House Robber (Linear)

  Problem: Array of house values. Cannot rob two adjacent houses. Maximize total. State: dp[i] = max money robbing from houses 0..i Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — skip this house or rob it (must skip previous)

• Decode Ways

  Problem: A message encoded as digits (1-26 → A-Z). Count ways to decode.

• Problems in This Family

  | Problem | Recurrence | |---------|-----------| | Climbing Stairs | dp[i] = dp[i-1] + dp[i-2] | | House Robber | dp[i] = max(dp[i-1], dp[i-2] + val[i]) | | Decode Ways | dp[i] = dp[i-1] (if valid 1-digit) + dp[i-2] (if valid 2-digit) |…

• Category 9: Grid DP

• Core Idea

  Navigate a 2D grid from one corner to another (or fill the grid with values). Each cell depends on its neighbors (typically above and left).

• Template

• Worked Example: Unique Paths

  Problem: Count all paths from top-left to bottom-right, moving only right or down. First row and first column are all 1s (only one way to reach them).

• Minimum Path Sum

  Problem: Find path from top-left to bottom-right minimizing sum of cells visited.

• Unique Paths with Obstacles

  If grid has obstacles (cells marked 1), set dp[i][j] = 0 for those cells.

• Maximal Square

  Problem: Find the largest square containing only 1s in a binary matrix. Key insight: dp[i][j] = side length of the largest square whose bottom-right corner is (i,j). A square of side k at (i,j) requires squares of side k-1 at all three n…

• Problems in This Family

  | Problem | Key Variation | |---------|--------------| | Unique Paths | Count paths (right/down only) | | Unique Paths II | With obstacles | | Minimum Path Sum | Minimize sum on path | | Maximal Square | Largest 1-square in binary matrix…

• Category 10: Kadane's Algorithm / Subarray DP

• Core Idea

  At each position, decide: extend the current subarray or start a new one here. This "extend or restart" decision is the simplest form of DP.

• Template

  State: dp[i] = maximum subarray sum ENDING at index i Transition: dp[i] = max(nums[i], dp[i-1] + nums[i]) — start fresh or extend

• Worked Example: Maximum Subarray Sum

• Maximum Circular Subarray

  Problem: The subarray can wrap around the end to the beginning. Key insight: Maximum circular subarray = max(standard Kadane, totalSum - minimum subarray). If the max sum wraps around, then the elements NOT in the subarray form a contigu…

• Maximum Product Subarray

  Variation: Track both max and min at each position (a negative times a negative becomes positive). Why track min? A large negative product can become the largest positive when multiplied by the next negative number.

• Problems in This Family

  | Problem | Twist | |---------|-------| | Maximum Subarray Sum | Classic Kadane | | Maximum Circular Subarray | max(Kadane, total - minKadane) | | Maximum Product Subarray | Track both max and min products | | Minimum Subarray Sum | Nega…

• 0/1 Knapsack: Additional Worked Variations

• Minimum Subset Sum Difference

  Problem: Partition array into two subsets to minimize the absolute difference of their sums. Reduction: If totalSum = S, we need subset with sum as close to S/2 as possible. Then min difference = S - 2bestSum.

• Target Sum (Assign + or - to Each Element)

  Problem: Assign + or - signs to each element to reach a target sum. Count the number of ways. Reduction: If S1 is the sum of elements with +, S2 is the sum with -: - S1 + S2 = totalSum - S1 - S2 = target - Therefore: S1 = (totalSum + tar…

• Count Subsets with Given Difference

  Problem: Count pairs of subsets (S1, S2) where S1 - S2 = diff. Reduction: S1 + S2 = totalSum, S1 - S2 = diff → S1 = (totalSum + diff) / 2 Then count subsets summing to S1. Identical to Target Sum after the reduction. ---

• Quick Reference: Identifying the Category

  ---

• Common Pitfalls

  1. Forgetting base cases: Always initialize dp[0], dp[empty], dp[single element] correctly 2. Off-by-one in indices: dp tables often have size n+1 to accommodate the empty prefix 3. Wrong loop direction: 0/1 knapsack needs right-to-left…

• Complexity Cheat Sheet

  | Category | Time | Space (optimized) | |----------|------|-------------------| | 0/1 Knapsack | O(n capacity) | O(capacity) | | Unbounded Knapsack | O(n capacity) | O(capacity) | | LCS | O(m n) | O(min(m, n)) | | LIS (DP) | O(n^2) |…

• Advanced DP Patterns

• Multi-Dimensional DP with Constraints — Counting Stable Arrays

  Problem type: Count arrangements of zeros and ones in a binary array such that no consecutive run of same value exceeds a given limit. State: dp[i][j][last] = number of ways to place i zeros and j ones, where the last placed digit is las…

• Maximum Strength from K Disjoint Subarrays

  Problem: Select exactly K non-overlapping subarrays to maximize a weighted "strength" formula where each subarray's sum is multiplied by a coefficient that alternates sign and decreases in magnitude. State: dp[i][j] = maximum strength ob…

• Summary: The DP Solving Framework

  1. Recognize the problem type using the Golden Rules 2. Identify which category it falls into 3. Define state: What parameters capture the subproblem? 4. Write transition: What choices do I have? How do states connect? 5. Determine order…