Top 40 Dynamic Programming Interview Questions 2025

DP solves problems by breaking into overlapping subproblems and storing results (memoization/tabulation). Use when: (1) Optimal substructure - optimal solution contains optimal solutions to subproblems, (2) Overlapping subproblems - same subproblems solved multiple times. Signs: counting ways, optimization (min/max), decision making at each step.

Memoization (top-down): recursive with caching, solve as needed, easier to implement, may have stack overhead. Tabulation (bottom-up): iterative, build table from smallest subproblems, no recursion overhead, may compute unnecessary states. Both achieve same time complexity. Tabulation often preferred for space optimization (only keep needed states).

Given items with weights and values, maximize value within weight capacity. DP: dp[i][w] = max value using first i items with capacity w. Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]). O(nW) time and space. Space optimize to O(W) by iterating weights backwards.

Find longest subsequence present in both strings. DP: dp[i][j] = LCS length for first i chars of s1, first j chars of s2. If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1, else: max(dp[i-1][j], dp[i][j-1]). O(mn) time/space. To reconstruct: backtrack from dp[m][n]. Space optimize to O(min(m,n)).

Patterns: (1) Linear DP - Fibonacci, climbing stairs, house robber, (2) Grid DP - unique paths, minimum path sum, (3) String DP - LCS, edit distance, palindrome, (4) Interval DP - matrix chain multiplication, burst balloons, (5) Knapsack - subset sum, coin change, (6) State machine - stock problems with cooldown/fee. Identify pattern, define state, find recurrence.