Dynamic Programming

Break problems into overlapping subproblems and build up solutions bottom-up.

26 problems 3 Easy 21 Medium 2 Hard

Overview

DP is the most-tested topic in senior interviews. The key insight is recognizing that the problem has optimal substructure and overlapping subproblems, then defining the state and transition clearly.

When to Use

Fibonacci and climbing stairs
Knapsack variants
Longest common subsequence
Coin change
Edit distance
House robber
Unique paths

Common Mistakes

Not defining the DP state clearly before coding
Missing base cases
Using top-down when bottom-up is simpler
Not realizing space can be optimized to O(1) or O(n)

Complexity

Time

Depends on state space — often O(n²) or O(n·m)

Space

O(n) with space optimization

// 1D DP (Climbing Stairs)
function climbStairs(n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1; dp[1] = 1;
  for (let i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
  return dp[n];
}

// 2D DP (Unique Paths)
function uniquePaths(m, n) {
  const dp = Array.from({length: m}, () => new Array(n).fill(1));
  for (let i = 1; i < m; i++)
    for (let j = 1; j < n; j++)
      dp[i][j] = dp[i-1][j] + dp[i][j-1];
  return dp[m-1][n-1];
}

Problems (26)

Hide completed

Problem	Difficulty	Companies	Freq
Climbing Stairs	Easy	AmazonAdobe +1	High
House Robber	Medium	AmazonGoogle +1	High
Coin Change	Medium	AmazonGoogle +2	High
Longest Increasing Subsequence	Medium	GoogleAmazon +1	High
Longest Common Subsequence	Medium	GoogleAmazon +1	High
Word Break	Medium	AmazonGoogle +2	High
Edit Distance	Hard	GoogleAmazon +2	Medium
Unique Paths	Medium	AmazonGoogle +1	High
Maximum Subarray	Medium	AmazonLinkedIn +2	High
Decode Ways	Medium	AmazonFacebook +1	High
Min Cost Climbing Stairs	Easy	AmazonGoogle +1	High
House Robber II	Medium	AmazonGoogle +1	High
Partition Equal Subset Sum	Medium	AmazonFacebook +1	High
Target Sum	Medium	FacebookAmazon +1	High
Best Time to Buy and Sell Stock	Easy	AmazonFacebook +3	High
Palindromic Substrings	Medium	FacebookAmazon +1	High
Longest Palindromic Substring	Medium	AmazonMicrosoft +2	High
Best Time to Buy and Sell Stock with Cooldown	Medium	AmazonGoogle	Medium
Maximum Product Subarray	Medium	AmazonGoogle +3	High
Triangle	Medium	AmazonApple	Medium
Minimum Path Sum	Medium	AmazonGoogle +1	High
Perfect Squares	Medium	GoogleAmazon	Medium
Regular Expression Matching	Hard	GoogleFacebook +2	Medium
Interleaving String	Medium	AmazonGoogle +1	Medium
Best Time to Buy and Sell Stock with Transaction Fee	Medium	AmazonGoogle	Medium
Integer Break	Medium	Google	Low

Dynamic programming looks hard until you realise 90% of interview DP problems follow the same four-s…

Enjoying this free content?

If this saved you time, buying me a coffee keeps new content coming.

☕ Buy me a coffee

Buy me a coffee