Dynamic Programming Types and Patterns

How to solve different types of DP problems asked in coding interviews

Photo by David White on Unsplash

Dynamic Programming is the most asked question in coding interviews due to three main reasons:

• It is hard to solve
• Difficult to find the pattern and the right approach to solve the problem.
• There are various types of Dynamic Programming Problems and different approaches to all those types.

In this article, I would be discussing the different types of Dynamic Programming problems, how to identify the patterns, and solve them with the right approach.

After solving more than fifty problems in Leetcode on Dynamic Programming I started to see some patterns, where few problems were similar to one another. The solution to those problems had the same approach.

For example, after solving the knapsack problem, I found it easy to solve the coin change problem as the solution was similar to that of the knapsack problem with the same approach.

Often the problems asked in interviews are the variations to these problems. So all we need to do is practice these different types of problems and when a problem with a similar pattern is given we need to apply the same approach to find the solution.

Pre-Requisites:

To Identify a Dynamic Programming Problem we need to know its properties:

• Overlapping subproblems
• Optimal Substructure

To read more about the basics of Dynamic Programming you can read this article I wrote:

Dynamic Programming Made Easy

How To approach a Dynamic Programming Problem In Interview:

• Identify the Pattern and type of Problem
• Identify the Base Cases
• Create a Recursive Solution and check for Overlapping Sub Problems
• Check for changing Parameters and Store the subproblems in a Table

Photo by Anthony Tran on Unsplash

I have Identified 5 important problems whose variations are asked in coding Interviews.

1. Knapsack 0/1

Problem Statement

Given the weights and profit of ’N’ items, put these items in a knapsack of capacity ‘W’ to get the maximum total value in the knapsack.

Input:
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
Output: 
220

Approach

There are two options for each weight, it can be included inside the knapsack or not. We calculate the maximum value obtained by either including or excluding the weight.

Solution

Variations

• Subset Sum Problem
• Equal Sum Partition problem
• Target Sum

2. Knapsack Unbounded

Problem Statement

Given the weights and values of ’N’ items, put these items in a knapsack of capacity ‘W’ to get the maximum total value in the knapsack with repetitions of items allowed.

Input:
W = 100
val = [10, 30, 20]
wt = [5, 10, 15]
Output:
300

Approach

In 0/1 Knapsack we either include or exclude a value but in Unbounded we can include it again and again as repetitions are allowed. We calculate the maximum value by either including or excluding the value and repeating the subproblem until the capacity is 0.

Solution

Variations

• Coin Change Problem
• Rod Cutting Problem
• Maximum Product Cutting

3. Longest Common Subsequence

Problem Statement

Given two sequences, find the length of the longest subsequence present in both of them.

Input:
X = "AGGTAB"
Y = "GXTXAYB"
Output:
GTAB

Approach

A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. We compare each character of the string and reduce the problem into subproblems and calculate the maximum possible value obtained by the subproblems.

Solution

Variations

• Longest Common Substring
• Shortest Common Supersequence
• Longest Palindromic Subsequence
• Longest Repeating Subsequence

4. Egg Dropping Problem

Problem Statement

You are given ‘K’ eggs and you have access to a building with ’N’ floors. Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor ‘F’ such that any egg dropped at a floor higher than ‘F’ will break, and any egg dropped at or below the floor ‘F’ will not break.

We need to find the minimum number of moves that you need to know the value of ‘F’.

Input:
n = 2, k = 10
Output:
4

Approach

In each move we have two choices:

• the egg breaks
• the egg doesn’t break

When there is just 1 egg left we don’t have a choice but to start from the 0th floor and check for the threshold floor.

When the egg breaks at floor ‘K’ we know that all floors above K are not threshold floor and the answer is below ‘K’.

When the egg does not break at floor ‘K’ we know that all floors below K are not threshold floor and the answer is above ‘K’.

From the above two cases, we need to select the worst possible scenario:

max( eggDrop(e-1,k-1) , eggDrop(e,n-k) )

Solution

Variations

• Matrix Chain Multiplication
• Word Break
• Palindromic Partitioning

5. DP with Grid — Unique Paths

Problem Statement

Count all the possible paths from top left to the bottom right of the matrix with the constraints that from each cell you can either move only to right or down

Input :  m = 2, n = 2
Output : 2
There are two paths
(0, 0) -> (0, 1) -> (1, 1)
(0, 0) -> (1, 0) -> (1, 1)

Approach

In this type of problem, we create a table and initialize the first row and first column value as 1 and each cell value is calculated by adding the values of the left cell and top cell.

Solution

Variations

• Rat in a Maze Problem
• Minimum Cost to Cover the given positions in a grid
• Maximum size square sub-matrix with all 1s

I hope after reading this article you would have got an idea of the different types of Dynamic Programming Problems and Patterns. The only way to master Dynamic Programming is to solve more and more problems.

Thank You for reading this article and Do follow me for more such articles!!!

References:

GeeksforGeeks | A computer science portal for geeks

Dynamic Programming - LeetCode