Types of Dynamic Programming Questions

Dynamic programming is probably the trickiest and most-feared interview question type. The hardest parts are 1) to know it’s a dynamic programming question to begin with 2) to find the subproblem.

We looked at a ton of dynamic programming questions and summarized common patterns and subproblems.

We also highlighted the keywords that indicate it’s likely a dynamic programming problem.

Sequence

This is the most common type of DP problem and a good place to get a feel of dynamic programming. In the recurrence relation, normally means max/min/best value for the sequence ending at index i.

  • House robber — find maximum amount of loot
  • Coin change — find minimum amount of coins needed to make up an amount

Grid

This is the 2D version of the sequence DP. means max/min/best value for matrix cell ending at index i, j.

  • Robot unique paths — number of ways for robot to move from top left to bottom right
  • Min path sum — find path in a grid with minimum cost
  • Maximal square — find maximal square of 1s in a grid of 0s and 1s

Dynamic number of subproblems

This is similar to “Sequence DP” except depends on a dynamic number of subproblems, e.g. .

  • Longest Increasing Subsequence — find the longest increasing subsequence of an array of numbers
  • Buy/sell stock with at most K transactions — maximize profit by buying and selling stocks using at most K transaction

Partition

This is a continuation of DFS + memoization problems. These problems are easier to reason and solve with a top-down approach. The key to solve these problems is to draw the state-space tree and then traverse it.

  • Decode ways — how many ways to decode a string
  • Word break — partition a word into words in a dictionary
  • Triangle — find the smallest sum path to traverse a triangle of numbers from top to bottom
  • Partition to Equal Sum Subsets — partition a set of numbers into two equal-sum subsets

Two Sequences

This type of problem has two sequences in their problem statement. represents the max/min/best value for the first sequence ending in index i and second sequence ending in index j.

  • Edit distance — find the minimum distance to edit one string to another
  • Longest common subsequence — find the longest common subsequence that is common in two sequences

Game theory

This type of problem asks for whether a player can win a decision game. The key to solving game theory problems is to identify winning state, and formulating a winning state as a state that returns a losing state to the opponent

  • Coins in a line
  • Divisor game
  • Stone game

Learn more about each type with detailed analysis and illustrations at AlgoMonster:

10x your algorithm interview prep speed. Take the 5-minute quiz: https://algo.monster/evaluator