# 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

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

# Grid

• 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

• 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

• 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

• 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

• Coins in a line
• Divisor game
• Stone game

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

## More from Algo.Monster

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