Online IDE
Free Mock
Events New Scaler
Improve your coding skills with our resources
Compete in popular contests with top coders
Attend free live masterclass hosted by top tech professionals
Explore Offerings by SCALER

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!


1. Why is dynamic programming named “dynamic”?

  • According to Richard Bellman’s autobiography “Eye of the Hurricane: An Autobiography (1984)”, the word “dynamic” was chosen by him to mainly capture the time-varying aspect of the problems.

2. How to recognize a problem that can be solved using Dynamic Programming?

  • DP is mainly an optimization technique. It is a method for solving problems by breaking them down into simpler subproblems and solving and storing the results of each subproblem just once. If the same subproblem occurs again, we look up the previously stored solution.
  • Hence, to recognize a problem and whether it can be solved using DP, ask yourself whether the given problem solution can be expressed as a function of solutions to similar smaller subproblems.

3. How to solve dynamic programming problems?

  • The concept of dynamic programming is very simple. If we have solved a problem with the given input, then we save the result for future reference, so as to avoid recomputing again.

  • We follow the mantra - Remember your Past.

    • If a given problem can be broken up in to smaller subproblems and these smaller subproblems can be in turn broken down in to even more smaller ones, and in this process, if we observe some subproblems which are already solved, then this is a big hint for us to use DP.
    • In case we are not storing the results, then we are bound to perform computations unnecessarily which goes against the principle of dynamic programming.  Image Source: Google
  • We need to know that the optimal solutions to each subproblem contribute to the optimal solution of the overall given problem.

  • We can follow the below steps as a guideline for coming up with a DP solution:

Step 1. Think of a recursive approach to solving the problem which essentially expresses a problem, say P(X), in terms of smaller subproblem, say P(Y) or an expression involving multiple smaller subproblems, say P(Yi). Here we expect Yi < X which could mean one of the following:
    a. If X is an integer, then it could mean Yi "less than" X arithmetically.
    b. If X is a string, it could mean that Yi is a substring of X.
    c. If X is an array, it could mean Yi is a subarray of X, and so forth.

Step 2. Once you have a approach, write a recursive code for that. Consider your recursive code function definition to be as below :
  solve(K1, K2, K3 ... )
Step 3. Keep track of the results of each function by saving them after every function call so that if the same function solve(K1, K2, K3 ... ) is called again, we need not compute again.

Step 4. Once we are done, analyze the space and time complexities of the solution developed, and try to improve them if possible.

And that’s how a DP problem is solved.

4. Difference between the top-down approach (memoization) and the bottom-up approach (tabulation)?

Parameters Memoization Tabulation
State definition State definition can be thought of easily. Complicated to identify what a state should represent
Ease of code Less complicated and easy to code. Complications increase when lots of other conditions arise.
Speed of execution Slower due to recursive calls and return statements Faster as state values are accessed directly from table.
Space The cache entries are filled on demand during memoization. All entries starting from the first one needs to be filled by default.

5. Where is dynamic programming used?

  • Dynamic programming is used in the cases where we solve problems by dividing them into similar suproblems and then solving and storing their results so that results are re-used later.
  • Used in the cases where optimization is needed.
  • Please refer to Application section above.

6. What are the characteristics of dynamic programming?

  • Every DP problem should have optimal substructure and overlapping subproblems. 

  • Please refer to the Characteristics of Dynamic Programming section above.

7. What are the applications of dynamic programming?

  • DP is almost used everywhere which requires a guaranteed optimal solution. It is heavily used in routing, graph problems, computer vision, computer networks, AI, machine learning etc.
  • Please refer to the Application section above.

8. How is dynamic programming different from the Greedy approach?

Greedy Algorithm vs Dynamic Programming

Parameters Dynamic Programming Greedy Approach
Optimality There is guaranteed optimal solution as DP considers all possible cases and then choose the best among them. Provides no guarantee of getting optimum approach.
Memory DP requires a table or cache for remembering and this increases it’s memory complexity. More memory efficient as it never looks back or revises its previous choices.
Time complexity DP is generally slower due to considering all possible cases and then choosing the best among them. Generally faster.
Feasibility Decision at each step is made after evaluating current problem and solution to previously solved subproblem to calculate optimal solution. Choice is made which seems best at the moment in the hope of getting global optimal solution.

9. How is dynamic programming different from the divide and conquer approach?

  • Divide and Conquer algorithm works by dividing a problem into subproblems, conquer by solving each subproblem recursively and then combine these solutions to get solution of the main problem.
    • Whereas DP is a optimization technique for solving problems in an optimised manner by dividing problem into smaller subproblems and then evaluating and storing their results and constructing an optimal solution for main problem from computed information.
  • The most important difference in Divide and Conquer strategy is that the subproblems are independent of each other. When a problem is divided into subproblems, they do not overlap which is why each subproblem is to be solved only once.
    • Whereas in DP, a subproblem solved as part of a bigger problem may be required to be solved again as part of another subproblem (concept of overlapping subproblem), so the results of a subproblem is solved and stored so that the next time it is encountered, the result is simply fetched and returned.

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
Jump Game Array 225 41:16
Min Jumps Array 300 71:56
Tree dp
Problem Score Companies Time Status
Max edge queries! 200 56:28
Max Sum Path in Binary Tree 400 55:20
Suffix / prefix dp
Derived dp
Problem Score Companies Time Status
Chain of Pairs 200 43:52
Max Sum Without Adjacent Elements 225 58:15
Merge elements 300 62:47
Problem Score Companies Time Status
Flip Array 200
Tushar's Birthday Party 200 72:32
0-1 Knapsack 200 48:53
Equal Average Partition 350 73:47
Problem Score Companies Time Status
Potions 200 53:59
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
Multiply dp
Problem Score Companies Time Status
Unique Binary Search Trees II 400 36:22
Count Permutations of BST 400
Breaking words
Problem Score Companies Time Status
Palindrome Partitioning II 400 62:49
Word Break 400
Excel at your interview with Masterclasses Know More
Certificate included
What will you Learn?
Free Mock Assessment
Fill up the details for personalised experience.
Phone Number *
OTP will be sent to this number for verification
+91 *
Change Number
Graduation Year *
Graduation Year *
*Enter the expected year of graduation if you're student
Current Employer
Company Name
College you graduated from
College/University Name
Job Title
Job Title
Engineering Leadership
Software Development Engineer (Backend)
Software Development Engineer (Frontend)
Software Development Engineer (Full Stack)
Data Scientist
Android Engineer
iOS Engineer
Devops Engineer
Support Engineer
Research Engineer
Engineering Intern
QA Engineer
Product Manager
Product Designer
Backend Architect
Program Manager
Release Engineer
Security Leadership
Database Administrator
Data Analyst
Non Coder
Please verify your phone number
Resend OTP
By clicking on Start Test, I agree to be contacted by Scaler in the future.
Already have an account? Log in
Free Mock Assessment
Instructions from Interviewbit
Start Test