Dynamic Programming Patterns

Here's the breakdown. 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,dp[i] normally means max/min/best value for the sequence ending at index i.

Grid

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

Dynamic number of subproblems

This is similar to "Sequence DP" except dp[i] depends on a dynamic number of subproblems, e.g. dp[i] = max(d[j]..) for j from 0 to i.

  • 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

Interval

The key to solve this type of problem involves finding subproblem defined on an interval dp[i][j].

Two Sequences

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

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

0-1 Knapsack Problem

This problem type has a series of objects and usually asks for the maximum value that can be achieved from the objects without achieving a certain weight