Dynamic Programming

4 problems using this pattern

About this pattern:

Break problems into subproblems and memoize results to avoid redundant computation.

Often used with: Array Fibonacci Knapsack LIS

Complexity Range

Time Complexity

O(n) (2 problems)
O(amount × coins) (1 problem)
O(n²) (1 problem)

Space Complexity

O(1) (2 problems)
O(amount) (1 problem)
O(n) (1 problem)

Problems Using Dynamic Programming

Climbing Stairs

Count distinct ways to climb n stairs (1 or 2 steps at a time).

Easy LeetCode
Time:
O(n)?
Why O(n)?
We calculate each step once from 2 to n
Instead of naive recursion (exponential), we use bottom-up DP to compute each step exactly once.
Example: For n=50, we do 48 iterations instead of 2^50 recursive calls
Space:
O(1)?
Why O(1)?
Only storing the last two values
We optimize space by only keeping prev2 and prev1 instead of an entire DP array.
Example: Uses same memory for n=10 or n=10,000
Example: n = 3 → 3 (1+1+1, 1+2, 2+1)
Dynamic Programming Fibonacci
View Solution →

House Robber

Rob houses in a line, but can't rob adjacent houses. Find maximum money.

Medium LeetCode
Time: O(n)
Space: O(1)
Example: [2,7,9,3,1] → 12 (rob houses 0,2,4)
Dynamic Programming Array
View Solution →

Coin Change

Find minimum number of coins needed to make the amount.

Medium LeetCode
Time: O(amount × coins)
Space: O(amount)
Example: coins=[1,3,4], amount=6 → 2 (3+3)
Dynamic Programming Knapsack
View Solution →

Longest Increasing Subsequence

Find the length of the longest strictly increasing subsequence.

Hard LeetCode
Time: O(n²)
Space: O(n)
Example: [10,9,2,5,3,7,101,18] → 4
Dynamic Programming LIS
View Solution →
← Back to All Patterns
View All Categories