Dynamic Programming Types and Patterns

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

Image for post
Image for post
Photo by David White on Unsplash

Pre-Requisites:

How To approach a Dynamic Programming Problem In Interview:

Image for post
Image for post
Photo by Anthony Tran on Unsplash

1. Knapsack 0/1

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

2. Knapsack Unbounded

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

3. Longest Common Subsequence

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

4. Egg Dropping Problem

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

5. DP with Grid — Unique Paths

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

References:

Self-taught Developer | Tech & Self Help Blogger | Exploring Life and Tech | Aim to Help Upcoming Software Developers in their Journey