What is the Dynamic Programming pattern?

The Dynamic Programming pattern is a systematic approach to solving a class of coding interview problems. By recognizing the Dynamic Programming structure, you can solve problems in optimal time complexity using proven techniques.

When should I use the Dynamic Programming pattern?

Use the Dynamic Programming pattern when the problem structure matches its recognition signals — typically when brute force would be O(n²) or worse, and the pattern reduces complexity to Varies (O(n) to O(n²) typically).

What is the time complexity of Dynamic Programming?

The Dynamic Programming pattern typically runs in Varies (O(n) to O(n²) typically) time and uses Same as time space. The exact complexity depends on the specific sub-variant being applied.

Is Dynamic Programming important for coding interviews?

Yes — the Dynamic Programming pattern is frequently tested at FAANG companies and competitive engineering interviews. Mastering this pattern gives you a reliable framework to solve many problem variations quickly.

How do I practice the Dynamic Programming pattern?

Start by studying the pattern's mental model and recognition signals on DSAPatterns, then practice the curated LeetCode problems below in order from Easy to Hard. Aim for pattern recognition before memorizing solutions.

← back to patterns

pattern / HARD

Dynamic Programming.

Solve complex problems by breaking into subproblems

complexity

time

Varies (O(n) to O(n²) typically)

space

Same as time

practice questions

browse and solve all 0 pattern questions →

02' — visual

interactive

Sliding window — k = 3

Maximum sum subarray

Window

[0, 2]

Sum

Step

0 / 3

03'

mental
model.

Define state, recurrence, base cases. Build up from base cases (bottom-up) or recurse with memoization (top-down).

DP solves problems by storing results of subproblems to avoid recomputation. Top-down (memoization) or bottom-up (tabulation).

when to use ✓

01Fibonacci, climbing stairs
02Longest common subsequence
03Knapsack problems
04Coin change
05Edit distance

when not ✗

01Greedy works
02No overlapping subproblems
03Divide and conquer is sufficient

04'

recognition signals

Overlapping subproblems

Optimal substructure

Choices at each step

Brute force is exponential

1D DP2D DPKnapsack (0/1, unbounded)LISLCSPartition DPBitmask DPDigit DPProbability DPState Machine DP

05'

templates

python

1# Beginner: Fixed-size sliding window
2def max_sum_k(nums, k):
3   n = len(nums)
4   if n < k:
5      return 0
6   window_sum = sum(nums[:k])
7   max_sum = window_sum
8   for i in range(k, n):
9      window_sum += nums[i] - nums[i - k]
10      max_sum = max(max_sum, window_sum)
11   return max_sum

common mistakes

01Wrong base cases
02Missing state dimensions
03Confusing min/max vs count

interview tips

01Identify state first, then transitions
02Practice 1D, 2D, and 3D DP
03Master knapsack, LCS, LIS

06'

practice this pattern

0 curated problems from LeetCode

See all

No questions found for this pattern yet.

07'

faq

1# Beginner: Fixed-size sliding window

2def max_sum_k(nums, k):

3 n = len(nums)

4 if n < k:

5 return 0

6 window_sum = sum(nums[:k])

7 max_sum = window_sum

8 for i in range(k, n):

9 window_sum += nums[i] - nums[i - k]

10 max_sum = max(max_sum, window_sum)

11 return max_sum