# Types of Dynamic Programming Questions

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**.

- 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. `dp[i][j]`

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 `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]`

.

- Number of ways to partition a string into palindromes.

## 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.

- 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

## 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

- 0-1 Knapsack Introduction