Cheatsheet›Dynamic Programming

CORE PATTERNVery High Frequency

Dynamic Programming

Dynamic Programming (DP) solves complex optimization and counting problems by breaking them down into simpler, overlapping subproblems. By storing the results of these subproblems (memoization for top-down, tabulation for bottom-up), it avoids redundant O(2^N) computations, reducing the complexity to polynomial time.

TimeO(N) to O(N*M)

SpaceO(N) to O(1)

DifficultyMedium to Hard

Key Insight

Store subproblem results — trade memory to avoid exponential recomputation.

Flip ⟲

Flip for Infographic

Interactive infographic on the flip side.

Click anywhere to Flip ⟲

FLIP SIDEDynamic Programming

Click anywhere to flip back ⟲

Recognition Signals (When to use this pattern)

→Optimal substructure present
→Overlapping subproblems
→Find min/max value or path
→Count total number of ways
→Decision at each index (pick/skip)
→String alignment or matching

Types of Problems (Subpatterns)

Each subpattern solves a specific type of problem. Click on a card to view its template.

1D DP & Linear Transitions

State depends on a constant number of previous elements (e.g., dp[i-1], dp[i-2]).

Common Problems

• Climbing Stairs
• House Robber
• Min Cost Climbing Stairs
• Decode Ways
• Integer Break

5 problems

Knapsack & Subset Sum

Decide whether to include or exclude items to achieve a target weight or sum constraint.

Common Problems

• Partition Equal Subset Sum
• Coin Change
• Target Sum
• Coin Change II
• Last Stone Weight II

5 problems

Longest Common Subsequence & String Alignment

Compare prefixes of two strings (size M and N) using a 2D grid.

Common Problems

• Longest Common Subsequence
• Edit Distance
• Longest Palindromic Subsequence
• Delete Operation for Two Strings
• Interleaving String

5 problems

Longest Increasing Subsequence & Decisions

Determine constraints on subsequences or maintain discrete state machine transitions.

Common Problems

• Longest Increasing Subsequence
• Best Time to Buy and Sell Stock with Cooldown
• Russian Doll Envelopes
• Largest Divisible Subset
• Longest String Chain

5 problems

Grid / Path & Matrix DP

Traverse a 2D board with specific direction constraints (e.g., right/down).

Common Problems

• Unique Paths
• Minimum Path Sum
• Maximal Square
• Unique Paths II
• Triangle

5 problems

Template / Approach

Template for: 1D DP & Linear Transitions

Define State

Define dp[i] to represent the answer (e.g., max profit, min cost, total ways) for the subproblem up to index i.

Identify Transition

Determine how dp[i] relates to previous states. E.g., dp[i] = dp[i-1] + dp[i-2] or dp[i] = max(dp[i-1], dp[i-2] + val).

Set Base Cases

Initialize the smallest subproblems directly. E.g., dp[0] = 1 (or 0), dp[1] = 1.

Optimize Space

If dp[i] only looks back a fixed distance (like 1 or 2 steps), replace the O(N) array with a few variables to achieve O(1) space.

template_cpp

💡 Standard 1D dynamic programming skeleton. This template tracks the last two states in variables to optimize space complexity from O(N) to O(1).

1// 1D DP space-optimized to O(1)
2int linearDP(int n)
3{
4   if (n <= 1) return n;
5 
6   int prev2 = 0;   // state for dp[i-2]
7   int prev1 = 1;   // state for dp[i-1]
8   int cur   = 0;   // state for dp[i]
9 
10   for (int i = 2; i <= n; i++)
11   {
12      // Example transition: dp[i] = dp[i-1] + dp[i-2]
13      cur   = prev1 + prev2;
14      prev2 = prev1;
15      prev1 = cur;
16   }
17 
18   return cur;
19}

Key Idea:Linear 1D DP structures solve problems where subproblem dependencies represent chronological or sequential order. When transition accesses only a fixed distance in history, replace the DP array with rotating scalar variables to reduce auxiliary space to O(1).

Practice Problems

Sharpen your skills with hand-picked problems.

View All Problems

Easy

Climbing Stairs

LeetCode #70

Medium

House Robber

LeetCode #198

Easy

Min Cost Climbing Stairs

LeetCode #746

Medium

Decode Ways

LeetCode #91

Medium

Partition Equal Subset Sum

LeetCode #416

Medium

Coin Change

LeetCode #322

Medium

Target Sum

LeetCode #494

Medium

Coin Change II

LeetCode #518

Medium

Longest Common Subsequence

LeetCode #1143

Hard

Edit Distance

LeetCode #72

Medium

Longest Palindromic Subsequence

LeetCode #516

Medium

Longest Increasing Subsequence

LeetCode #300

Medium

Best Time to Buy and Sell Stock with Cooldown

LeetCode #309

Medium

Longest String Chain

LeetCode #1048

Medium

Unique Paths

LeetCode #62

Medium

Minimum Path Sum

LeetCode #64

Medium

Maximal Square

LeetCode #221

Dynamic Programming

1// 1D DP space-optimized to O(1)

2int linearDP(int n)

4 if (n <= 1) return n;

6 int prev2 = 0; // state for dp[i-2]

7 int prev1 = 1; // state for dp[i-1]

8 int cur = 0; // state for dp[i]

10 for (int i = 2; i <= n; i++)

11 {

12 // Example transition: dp[i] = dp[i-1] + dp[i-2]

13 cur = prev1 + prev2;

14 prev2 = prev1;

15 prev1 = cur;

16 }

18 return cur;

19}