Practice
Resources
Contests
Online IDE
New
Free Mock
Scaler
Practice
Improve your coding skills with our resources
Contests
Compete in popular contests with top coders
Scaler
Explore Offerings by SCALER

Welcome to Interviewbit, help us create the best experience for you!

Currently, You are a:

Few details about your education

College/University *
Enter the name of your college
Branch *
Year of completion *

Few details about your education

College/University *
Enter the name of your college
Branch *
Year of completion *

Few details about your career...

Current Company *
Enter company name
Experience *

You're all set!

Begin your success journey!

Sign Up using
Full name *
Email *
Password *

By creating an account, I acknowledge that I have read and agree to InterviewBit’s Terms and Privacy Policy .

Welcome back!

Log In using
Email *
Password *

Dynamic Programming

Go to Problems

Level 1

Jump to Level 2

Level 2

Jump to Level 3

Level 3

Jump to Level 4

Level 4

Jump to Level 5

Level 5

Jump to Level 6

Level 6

Jump to Level 7

Level 7

Jump to Level 8

Level 8

Be a Code Ninja!

Applications

Before diving into DP, let us first understand where do we use DP.

The core concept of DP is to avoid repeated work by remembering partial results (results of subproblems). This is very critical in terms of boosting performance and speed of algorithm. Most of the problems in computer science and real world can be solved using DP technique.

  • In real life scenarios, consider the example where I have to go from home to work everyday. For the first time, I can calculate the shortest path between home and work by considering all possible routes. But, it is not feasible to do the calculation every day. Hence, I will be memorizing that shortest path and will be following that route everyday. In computer science terms, Google Maps will be using DP algorithm to find the shortest paths between two points.

  • Largest Common Subsequence (LCS) problem - Basis of data comparison problems and to identify plagiarism in the contents.

  • Longest Increasing Subsequence problem - used in DNA Matching between two individuals. Generally, the DNAs are represented as strings and to form a match between DNAs of two individuals, the algorithm needs to find out the longest increasing sub sequence between them. In cases of DNA match, the longest common sub-string (LCS) is also found.

  • Knapsack Problem You have a bag of limited capacity and you decide to go on a challenging trek. Due to the capacity restriction, you can only carry certain items in optimum quantity. How do you select the materials and its quantity in efficient manner so that you don’t miss out on important items? That’s where DP comes into aid. 

  • Apart from the above, DP has found its importance in various fields like Bioinformatics, Operations research, Decision Making, Image Processing, MATLAB, MS Word, MS Excel, Financial Optimisations, Genetics, XML indexing and querying and what not! Read More.

Serious about Learning Programming ?

Learn this and a lot more with Scaler Academy's industry vetted curriculum which covers Data Structures & Algorithms in depth.

Dynamic Programming Problems

Greedy or dp
Problem Score Companies Time Status
Tushar's Birthday Bombs 200
78:13
Jump Game Array 225 41:16
Min Jumps Array 300 71:44
Tree dp
Problem Score Companies Time Status
Max edge queries! 200 56:34
Max Sum Path in Binary Tree 400 55:07
Suffix / prefix dp
Derived dp
Problem Score Companies Time Status
Chain of Pairs 200 42:09
Max Sum Without Adjacent Elements 225 58:10
Merge elements 300 57:43
Knapsack
Problem Score Companies Time Status
Flip Array 200
78:42
Tushar's Birthday Party 200 70:50
0-1 Knapsack 200 47:57
Equal Average Partition 350 71:48
Adhoc
Problem Score Companies Time Status
Best Time to Buy and Sell Stocks II 225 40:18
Dp optimized backtrack
Problem Score Companies Time Status
Word Break II 350
IBM
67:29
Multiply dp
Problem Score Companies Time Status
Unique Binary Search Trees II 400 36:06
Count Permutations of BST 400
62:18
Breaking words
Problem Score Companies Time Status
Palindrome Partitioning II 400 62:02
Word Break 400
IBM
67:00

Additional Practice

Problem Score Companies Time Status
Potions 200 56:52
Dice Throw 400 49:10
Double Increasing Series 200 45:07
Dice Rolls 300 27:32
Palindromic Substrings 200
LTI
25:36
Free Mock Assessment
Help us know you better for the best experience
Current Employer *
Enter company name
College you graduated from *
Enter university name
Phone Number *
OTP will be sent to this number for verification
+1
+1
Change Number
Edit
Resend OTP
By Continuing I agree to be contacted by Scaler in the future.
Already have an account? Log in