## Follow these steps to solve any Dynamic Programming interview problem

by Nikola Otasevic

Despite having significant experience building software products, many engineers feel jittery at the thought of going through a coding interview that focuses on algorithms. I’ve interviewed hundreds of engineers at Refdash , Google, and at startups I’ve been a part of, and some of the most common questions that make engineers uneasy are the ones that involve Dynamic Programming (DP).

Many tech companies like to ask DP questions in their interviews. While we can debate whether they’re effective in evaluating someone’s ability to perform in an engineering role, DP continues to be an area that trips engineers up on their way to finding a job that they love.

## Dynamic Programming — Predictable and Preparable

## 7 Steps to solve a Dynamic Programming problem

- How to recognize a DP problem
- Identify problem variables
- Clearly express the recurrence relation
- Identify the base cases
- Decide if you want to implement it iteratively or recursively
- Add memoization
- Determine time complexity

## Sample DP Problem

## Problem statement:

In this problem, we’re on a crazy jumping ball, trying to stop, while avoiding spikes along the way.

## Here are the rules:

3) Every time you land on a spot, you can adjust your speed by up to 1 unit before the next jump.

## Step 1: How to recognize a Dynamic Programming problem

Recognizing a Dynamic Programming problem is often the most difficult step in solving it. Can the problem solution be expressed as a function of solutions to similar smaller problems?

## Step 2: Identify problem variables

In our example, the two parameters that could change for every subproblem are:

Identify the changing parameters and determine the number of subproblems.

## Step 3: Clearly express the recurrence relation

Here is how we think about it in our sample problem:

More formally, if our speed is S, position P, we could go from (S, P) to:

- (S, P + S) ; # if we do not change the speed
- (S — 1, P + S — 1) ; # if we change the speed by -1
- (S + 1, P + S + 1) ; # if we change the speed by +1

canStop(S, P) = canStop(S, P + S) || canStop(S — 1, P + S — 1) || canStop(S + 1, P + S + 1)

Woohoo, it seems like we have our recurrence relation!

Recurrence relation: Assuming you have computed the subproblems, how would you compute the main problem?

## Step 4: Identify the base cases

- P should be within the bounds of the given runway
- P cannot be such that runway[P] is false because that would mean that we’re standing on a spike
- S cannot be negative, and a S==0 indicates that we’re done

- P < 0 || P >= length of runway seems like the right thing to do. An alternative could be to consider m aking P == end of runway a base case. However, it is possible that a problem splits into a subproblem which goes beyond the end of the runway, so we really need to check for inequality.
- This seems pretty obvious. We can simply check if runway[P] is false .
- Similar to #1, we could simply check for S < 0 and S == 0. However, here we can reason that it is impossible for S to be < 0 because S decreases by at most 1, so it would have to go through S == 0 case beforehand. Ther efore S == 0 is a sufficient base case for the S parameter.

## Step 5: Decide if you want to implement it iteratively or recursively

An iterative solution: (original code snippets can be found here )

## Step 6: Add memoization

- Store your function result into your memory before every return statement
- Look up the memory for the function result before you start doing any other computation

- I created a runway of length 1000 with spikes in random places (I chose to have a probability of a spike being in any given spot to be 20%)
- initSpeed = 30
- I ran all functions 10 times and measured the average time of execution

Here are the results (in seconds):

## Step 7: Determine Time complexity

- Count the number of states — this will depend on the number of changing parameters in your problem
- Think about the work done per each state. In other words, if everything else but one state has been computed, how much work do you have to do to compute that last state?

In our example problem, the number of states is |P| * |S|, where

For a runway of length L , the following has to hold:

=> (S-1) + (S-2) + (S-3) + ….+ 1 < L

If you find roots of the above function, they will be:

r1 = 1/2 + sqrt(1/4 + 2L) and r2 = 1/2 — sqrt(1/4 + 2L)

We can write our inequality as:

Considering that S — r2 > 0 for any S > 0 and L > 0, we need the following:

S — 1/2 — sqrt(1/4 + 2L) < ; 0

O(L * sqrt(L)) which is better than O(L²)

O(L * sqrt(L)) is the upper bound on the time complexity

Awesome, you made it through! :)

## Here are some next steps that you can take

- Extend the sample problem by trying to find a path to a stopping point. We solved a problem that tells you whether you can stop, but what if you wanted to also know the steps to take in order to stop eventually along the runway? How would you modify the existing implementation to do that?
- If you want to solidify your understanding of memoization, and understand that it is just a function result cache, you should read about decorators in Python or similar concepts in other languages. Think about how they would allow you to implement memoization in general for any function that you want to memoize.
- Work on more DP problems by following the steps we went through. You can always find a bunch of them online (ex. LeetCode or GeeksForGeeks ). As you practice, keep in mind one thing: learn ideas, don’t learn problems. The number of ideas is significantly smaller and it’s an easier space to conquer which will also serve you much better.

If this article was helpful, tweet it .

- Android App Development (Live)
- Data Science (Live)
- DSA for Interview Preparation
- DSA Live for Working Professionals
- DSA Self-paced in C++/Java
- DSA Self-paced in Python
- DSA Self-paced in Javascript
- DSA Self-paced in C
- Data Structure & Algorithm Classes (Live)
- System Design (Live)
- DevOps(Live)
- Data Structures & Algorithms in JavaScript
- Explore More Live Courses
- Interview Preparation Course
- GATE CS & IT 2024
- Data Structure & Algorithm-Self Paced(C++/JAVA)
- Data Structures & Algorithms in Python
- Explore More Self-Paced Courses
- C++ Programming - Beginner to Advanced
- Java Programming - Beginner to Advanced
- C Programming - Beginner to Advanced
- Full Stack Development with React & Node JS(Live)
- Java Backend Development(Live)
- Android App Development with Kotlin(Live)
- Python Backend Development with Django(Live)
- Complete Data Science Program(Live)
- Mastering Data Analytics
- DevOps Engineering - Planning to Production
- CBSE Class 12 Computer Science
- School Guide
- All Courses
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- Doubly Circular linked list
- Generic Tree
- Binary Tree
- Binary Search Tree
- Red Black Tree
- All Tree Data Structures
- Set Data Structure
- Map Data Structure
- Advanced Data Structure
- All Data Structures
- Design and Analysis of Algorithms
- Asymptotic Analysis
- Worst, Average and Best Cases
- Asymptotic Notations
- Little o and little omega notations
- Lower and Upper Bound Theory
- Analysis of Loops
- Solving Recurrences
- Amortized Analysis
- What does 'Space Complexity' mean ?
- Pseudo-polynomial Algorithms
- Polynomial Time Approximation Scheme
- A Time Complexity Question
- Linear Search
- Binary Search
- All Searching Algorithms
- Selection Sort
- Bubble Sort
- Insertion Sort
- Counting Sort
- Bucket Sort
- All Sorting Algorithms
- Greedy Algorithms
- Dynamic Programming
- Graph Algorithms
- Pattern Searching
- Backtracking
- Divide and Conquer
- Geometric Algorithms
- Mathematical
- Bitwise Algorithms
- Randomized Algorithms
- Branch and Bound
- All Algorithms
- What is System Design
- Key Terminologies in System Design
- Analysis and Architecture of Systems
- Scalability in System Design
- Databases in System Design
- High Level Design or HLD
- Low Level Design or LLD
- Communication Protocols
- Web Servers and Proxies
- Case Studies in Designing Systems
- Complete System Design Tutorial
- Factory Pattern
- Observer Pattern
- Singleton Design Pattern
- Decorator Pattern
- Strategy Pattern
- Adapter Pattern
- Command Pattern
- Iterator Pattern
- Prototype Design Pattern
- All Design Patterns
- Company Preparation
- Practice Company Questions
- Interview Experiences
- Experienced Interviews
- Internship Interviews
- Competitive Programming
- Multiple Choice Quizzes
- Aptitude for Placements
- Go Language
- Tailwind CSS
- Foundation CSS
- Materialize CSS
- Semantic UI
- Angular PrimeNG
- Angular ngx Bootstrap
- jQuery Mobile
- jQuery EasyUI
- React Bootstrap
- React Rebass
- React Desktop
- React Suite
- ReactJS Evergreen
- ReactJS Reactstrap
- BlueprintJS
- TensorFlow.js
- English Grammar
- School Programming
- Number System
- Trigonometry
- Probability
- Mensuration
- Class 8 Syllabus
- Class 9 Syllabus
- Class 10 Syllabus
- Class 11 Syllabus
- Class 12 Syllabus
- Class 8 Notes
- Class 9 Notes
- Class 10 Notes
- Class 11 Notes
- Class 12 Notes
- Class 8 Formulas
- Class 9 Formulas
- Class 10 Formulas
- Class 11 Formulas
- Class 8 Maths Solution
- Class 9 Maths Solution
- Class 10 Maths Solution
- Class 11 Maths Solution
- Class 12 Maths Solution
- Class 7 SS Syllabus
- Class 8 SS Syllabus
- Class 9 SS Syllabus
- Class 10 SS Syllabus
- Class 7 Notes
- History Class 7
- History Class 8
- History Class 9
- Geo. Class 7
- Geo. Class 8
- Geo. Class 9
- Civics Class 7
- Civics Class 8
- Business Studies (Class 11th)
- Microeconomics (Class 11th)
- Statistics for Economics (Class 11th)
- Business Studies (Class 12th)
- Accountancy (Class 12th)
- Macroeconomics (Class 12th)
- Political Science
- Machine Learning
- Data Science
- Microsoft Azure Tutorial
- Google Cloud Platform
- Mathematics
- Operating System
- Computer Networks
- Computer Organization and Architecture
- Theory of Computation
- Compiler Design
- Digital Logic
- Software Engineering
- GATE 2024 Live Course
- GATE Computer Science Notes
- Last Minute Notes
- GATE CS Solved Papers
- GATE CS Original Papers and Official Keys
- GATE CS 2023 Syllabus
- Important Topics for GATE CS
- GATE 2023 Important Dates
- ISRO CS Original Papers and Official Keys
- ISRO CS Solved Papers
- ISRO CS Syllabus for Scientist/Engineer Exam
- UGC NET CS Notes Paper II
- UGC NET CS Notes Paper III
- UGC NET CS Solved Papers
- HTML Cheat Sheet
- CSS Cheat Sheet
- Bootstrap Cheat Sheet
- JS Cheat Sheet
- jQuery Cheat Sheet
- Angular Cheat Sheet
- Facebook SDE Sheet
- Amazon SDE Sheet
- Apple SDE Sheet
- Netflix SDE Sheet
- Google SDE Sheet
- Wipro Coding Sheet
- Infosys Coding Sheet
- TCS Coding Sheet
- Cognizant Coding Sheet
- HCL Coding Sheet
- FAANG Coding Sheet
- Love Babbar Sheet
- Mass Recruiter Sheet
- Product-Based Coding Sheet
- Company-Wise Preparation Sheet
- Array Sheet
- String Sheet
- Graph Sheet
- Geography Notes
- Modern Indian History Notes
- Medieval Indian History Notes
- Ancient Indian History Notes
- Complete History Notes
- Science & Tech. Notes
- Ethics Notes
- Polity Notes
- Economics Notes
- Government Schemes (Updated)
- UPSC Previous Year Papers
- Campus Ambassador Program
- School Ambassador Program
- Geek of the Month
- Campus Geek of the Month
- Placement Course
- Testimonials
- Student Chapter
- Geek on the Top
- SSC CGL Syllabus
- General Studies
- Subjectwise Practice Papers
- Previous Year Papers
- SBI Clerk Syllabus
- General Awareness
- Quantitative Aptitude
- Reasoning Ability
- SBI Clerk Practice Papers
- SBI PO Syllabus
- SBI PO Practice Papers
- IBPS PO 2022 Syllabus
- English Notes
- Reasoning Notes
- Mock Question Papers
- IBPS Clerk Syllabus
- Corporate Hiring Solutions
- Apply through Jobathon
- Apply for a Job
- All DSA Problems
- Problem of the Day
- GFG SDE Sheet
- Top 50 Array Problems
- Top 50 String Problems
- Top 50 Tree Problems
- Top 50 Graph Problems
- Top 50 DP Problems
- GFG Weekly Coding Contest
- Job-A-Thon: Hiring Challenge
- BiWizard School Contest
- All Contests and Events
- Saved Videos
- What's New ?
- Data Structures
- Linked List
- Divide & Conquer

## Related Articles

- Write an Interview Experience
- Write an Admission Experience
- What is memoization? A Complete tutorial
- Introduction to Dynamic Programming – Data Structures and Algorithm Tutorials
- Tabulation vs Memoization
- Optimal Substructure Property in Dynamic Programming | DP-2
- Overlapping Subproblems Property in Dynamic Programming | DP-1

## How to solve a Dynamic Programming Problem ?

- Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique cap to every person)
- Digit DP | Introduction
- Sum over Subsets | Dynamic Programming
- Coin Change | DP-7
- Subset Sum Problem | DP-25
- Introduction and Dynamic Programming solution to compute nCr%p
- Cutting a Rod | DP-13
- Painting Fence Algorithm
- Longest Common Subsequence (LCS)
- Longest Increasing Subsequence (LIS)
- Longest subsequence such that difference between adjacents is one
- Maximum size square sub-matrix with all 1s
- Min Cost Path | DP-6
- Longest Common Substring (Space optimized DP solution)
- Count ways to reach the nth stair using step 1, 2 or 3
- Count all possible paths from top left to bottom right of a mXn matrix
- Unique paths in a Grid with Obstacles
- 0/1 Knapsack Problem
- Printing Items in 0/1 Knapsack
- Unbounded Knapsack (Repetition of items allowed)
- Egg Dropping Puzzle | DP-11
- Word Break Problem | DP-32
- Vertex Cover Problem (Dynamic Programming Solution for Tree)
- Tile Stacking Problem
- Box Stacking Problem | DP-22
- Partition problem | DP-18
- Travelling Salesman Problem using Dynamic Programming
- Longest Palindromic Subsequence | DP-12
- Longest Common Increasing Subsequence (LCS + LIS)
- Find all distinct subset (or subsequence) sums of an array
- Weighted Job Scheduling
- Count Derangements (Permutation such that no element appears in its original position)
- Minimum insertions to form a palindrome | DP-28
- Ways to arrange Balls such that adjacent balls are of different types
- Palindrome Partitioning | DP-17
- Word Wrap Problem | DP-19
- The Painter’s Partition Problem
- Program for Bridge and Torch problem
- Matrix Chain Multiplication | DP-8
- Printing brackets in Matrix Chain Multiplication Problem
- Maximum sum rectangle in a 2D matrix | DP-27
- Maximum profit by buying and selling a share at most k times
- Minimum cost to sort strings using reversal operations of different costs
- Count of AP (Arithmetic Progression) Subsequences in an array
- Introduction to Dynamic Programming on Trees
- Maximum height of Tree when any Node can be considered as Root
- Longest repeating and non-overlapping substring
- Discuss(50+)

Dynamic Programming (DP) is a technique that solves some particular type of problems in Polynomial Time . Dynamic Programming solutions are faster than the exponential brute method and can be easily proved their correctness.

## To dynamically solve a problem, we need to check two necessary conditions:

- Overlapping Subproblems : W hen the solutions to the same subproblems are needed repetitively for solving the actual problem. The problem is said to have overlapping subproblems property.
- Optimal Substructure Property : I f the optimal solution of the given problem can be obtained by using optimal solutions of its subproblems then the problem is said to have Optimal Substructure Property.

## Steps to solve a Dynamic programming problem:

- Identify if it is a Dynamic programming problem.
- Decide a state expression with the Least parameters.
- Formulate state and transition relationship.
- Do tabulation (or memorization).

## Step 1: How to classify a problem as a Dynamic Programming Problem?

- Typically, all the problems that require maximizing or minimizing certain quantities or counting problems that say to count the arrangements under certain conditions or certain probability problems can be solved by using Dynamic Programming.
- All dynamic programming problems satisfy the overlapping subproblems property and most of the classic Dynamic programming problems also satisfy the optimal substructure property. Once we observe these properties in a given problem be sure that it can be solved using Dynamic Programming.

## Step 2: Deciding the state

A state can be defined as the set of parameters that can uniquely identify a certain position or standing in the given problem. This set of parameters should be as small as possible to reduce state space.

## Step 3: Formulating a relation among the states

The total number of ways to form 6 is: 8 1+1+1+1+1+1 1+1+1+3 1+1+3+1 1+3+1+1 3+1+1+1 3+3 1+5 5+1

The steps to solve the given problem will be:

- We decide a state for the given problem.
- We will take a parameter N to decide the state as it uniquely identifies any subproblem.
- DP state will look like state(N), state(N) means the total number of arrangements to form N by using {1, 3, 5} as elements. Derive a transition relation between any two states.
- Now, we need to compute state(N).

1) Adding 1 to all possible combinations of state (n = 6) Eg : [ (1+1+1+1+1+1) + 1] [ (1+1+1+3) + 1] [ (1+1+3+1) + 1] [ (1+3+1+1) + 1] [ (3+1+1+1) + 1] [ (3+3) + 1] [ (1+5) + 1] [ (5+1) + 1] 2) Adding 3 to all possible combinations of state (n = 4); [(1+1+1+1) + 3] [(1+3) + 3] [(3+1) + 3] 3) Adding 5 to all possible combinations of state(n = 2) [ (1+1) + 5] (Note how it sufficient to add only on the right-side – all the add-from-left-side cases are covered, either in the same state, or another, e.g. [ 1+(1+1+1+3)] is not needed in state (n=6) because it’s covered by state (n = 4) [(1+1+1+1) + 3]) Now, think carefully and satisfy yourself that the above three cases are covering all possible ways to form a sum total of 7; Therefore, we can say that result for state(7) = state (6) + state (4) + state (2) OR state(7) = state (7-1) + state (7-3) + state (7-5) In general, state(n) = state(n-1) + state(n-3) + state(n-5)

Below is the implementation of the above approach:

## Step 4: Adding memoization or tabulation for the state

Adding memoization to the above code

You may check the below problems first and try solving them using the above-described steps:-

This article is contributed by Nitish Kumar . If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to [email protected]. See your article appearing on the GeeksforGeeks main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Solve DSA problems on GfG Practice.

## Please Login to comment...

- GauriShankarBadola
- prashant11_4
- ayushbhardwaj1
- srivastavaharshit848
- dharanendralv23
- avanitrachhadiya2155
- shankarmoturi29
- abhijeet19403
- 4wwcz6wjzcry0i65yxjbviufuxk0z8itc3ix23cn
- aashutoshparoha

## Data Structures and Algorithms - Self Paced

## Data Structures & Algorithms in Python - Self Paced

## Data Structures & Algorithms in JavaScript - Self Paced

Improve your coding skills with practice.

LTCWM > Blog > Resources > Technical guides > How to Solve Any Dynamic Programming Problem

## How to Solve Any Dynamic Programming Problem

Updated on April 12th, 2020 | Sign up for learn to code tips

If you’re aiming for a top-tier tech job, you have to face the coding interview —and come out on top. And one sure-fire way to impress is to have dynamic programming down pat.

In today’s special guest post, Sam Gavis-Hughson guides us through his formula for solving any dynamic programming problem.

Take it away, Sam!

Disclosure: I’m an affiliate for Sam's courses. While the resources mentioned in this post are free, I may get a small commission if you click the links below and later buy one of his products. Thanks!

When it comes to coding interviews , not all topics are created equal.

Some are relatively easy. For example, even the hardest linked list problems don’t tend to be that difficult because the concept is on the simpler side.

But then there are some topics where even the easiest variations strike fear into the hearts of interviewees everywhere.

One such topic is dynamic programming—an optimization technique programmers can use to speed up our code when we are repeatedly solving the same problem.

Dynamic programming has truly become the defacto hard topic that your interviewer can ask you. If they want to really put you through your paces, that’s what they’ll ask about.

This means that if you’re interviewing for any top tech company , dynamic programming should be at the top of your list of topics to prepare.

## What is Dynamic Programming?

Essentially, dynamic programming is a way of making a recursive algorithm more efficient by making sure it doesn’t have to solve the same subproblem twice.

When you use dynamic programming, it stores the results of subproblems so you don’t have to re-compute those results next time they’re needed. It’s an alternative to plain recursion, which requires repeating the solution process every time the subproblem is encountered.

This Stack Overflow answer words it well: “Dynamic programming is when you use past knowledge to make solving a future problem easier.”

Some benefits of dynamic programming are that it saves you coding time, reduces lines of code, and speeds up an algorithm’s processing time.

Now, here’s the crazy thing…

## Dynamic Programming Doesn’t Have to Be Hard

The real challenge with dynamic programming is that it is counterintuitive. When you’re trying to solve dynamic programming problems, all the obvious steps that you would normally take actually pull you further away from the correct solution:

- Want to find the optimal solution? You actually need to start with the brute force approach.
- Want to find an iterative solution? You have to start with recursion.
- Want to solve the problem as quickly as possible? You need to slow it down and go step by step.

Click To Tweet

So if dynamic programming is so counterintuitive, how are we ever supposed to solve these problems effectively?

To start, let’s look at how most people prepare for their coding interviews:

They focus on memorizing solutions.

Rather than being strategic and understanding the underlying techniques, most people focus on simply memorizing as many solutions as they can.

Memorizing gives you a quick and easy win. But the problem is that it ultimately handicaps you.

When you focus on memorizing, your interview prep strategy becomes very simple: just go through as many problems as you can. When you go into an interview, you hope that you see a problem that you’ve studied before.

But this approach quickly leads to diminishing returns. There’s only so much that you can actually memorize, and the number of problems that you could be asked is very large.

Not to mention that this approach prevents you from actually being able to connect the dots.

Imagine learning a new language (let’s say French). You decide that you are going to create a massive deck of flashcards and simply memorize individual words. This is your plan to get to fluency.

So you start memorizing. Here’s one sample set of words:

“suis”, “es”, “est”, “sommes”, “êtez”, “sont”

What is the connection between these words (if you already know French, pretend you don’t for a sec)?

On the surface, it’s not obvious. So if you were just memorizing, you would be memorizing 6 discrete words.

However, there actually is a very close connection between these words: They’re all different conjugations of the verb “to be.”

If we look at the translations, we see:

- “Je suis” – “I am”
- “Tu es” – “You are”
- “Elle est” – “She is”
- “Nous sommes” – “We are”
- “Vous êtez” – “You all are”
- “Ils sont” – “They are”

Notice how much easier this is now that we’ve connected them all in some way that is meaningful to us? Yes we still need to memorize the specifics, but now we can see what connects them.

So what if we could do the same thing with dynamic programming?

Well, it’s never going to happen if we just try to memorize solutions to different problems. The issue is that the similarity between these different problems ISN’T in the solution itself.

The similarity between all dynamic programming problems is in the process.

For the rest of this post, I’m going to show you the exact strategy that you can use to solve any dynamic programming problem, even if you’ve never seen the problem before.

The remainder of this post is excerpted from my free ebook, Dynamic Programming for Interviews, which you can download here .

## How to Solve Dynamic Programming Problems Using the Fast Method

What is the most important characteristic of any successful interviewee?

They have a repeatable strategy.

That’s exactly what the FAST Method is. It’s a repeatable strategy for solving any dynamic programming problem, whether you’ve seen the problem before or not.

The FAST Method is an acronym for the 4 steps you need to solve any dynamic programming problem:

- F ind the First Solution
- A nalyze the First Solution
- Identify the S ubproblems
- T urn around the solution

By following these 4 steps, you’ll be able to find the optimal dynamic programming solution for any problem.

Start coding now

Stop waiting and start learning! Get my 10 tips on teaching yourself how to code.

Success! Now check your email to confirm your subscription.

There was an error submitting your subscription. Please try again.

## 1. Find the First Solution

The first step for any dynamic programming problem (and the step that most people skip) is to find an initial brute-force solution to the problem.

The goal here is to just get something down on paper without any concern for efficiency. To be honest, this should be the first step for any problem you might solve, but it is particularly important for dynamic programming.

There are several keys to think about while doing this step that you’ll want to keep in mind:

- The solution should be recursive. If not, the problem probably isn’t a good candidate for dynamic programming. For a lot more info on effectively coming up with a recursive solution, look here .
- Each recursive call must be self-contained. This means that you cannot store your results to a global variable or pass a results variable into your function. I often refer to the required approach as “building up as you return” and you can learn more about that here .
- It is important that we minimize the number of variables that we are passing into our recursive function. Dynamic programming solutions rely on there being multiple recursive calls with the same input, and the more variables there are, the less the inputs will overlap.

With these basic rules in mind, you will have no trouble using this brute force solution in the FAST Method.

Check out Dynamic Programming for Interviews for detailed walkthroughs of 5 of the most popular dynamic programming problems.

## 2. Analyze the First Solution

This is the step where we decide whether we can actually use dynamic programming to solve a problem. To do this, we’re going to look at a couple of specific things.

First off, we should be sure to determine what the actual time complexity of our code is currently. One mistake that I see fairly often is attempting to optimize something that doesn’t need to be optimized. If our solution is already efficient, spending a lot of time optimizing is a real waste of time.

With most of our recursive functions, we can use a pretty simple heuristic to compute the runtime. We simply look at the branching factor of our recursive function raised to the depth.

For example, if we were finding all combinations of an input, that would give us a time complexity of `O(2n)`. You can read a lot more about this here .

Next up, if our solution is in fact inefficient (we’re most likely looking for something that is exponential time or worse as being inefficient), we want to see if we can optimize it using dynamic programming.

Dynamic programming actually requires us to meet 2 specific criteria. If we don’t, then it is not possible for us to optimize our problem using dynamic programming. However, if we do, we will likely see a major improvement.

These are the criteria that we need to look for:

## Optimal Substructure

The first criterion is that our problem must have optimal substructure. Technically speaking, this means that we must be able to find an optimal solution to a problem by solving for its subproblems. An easier way to think about this is simply that we must be able to solve the problem recursively. If we already found a recursive problem in the previous step, then we can safely assume we have optimal substructure.

## Overlapping Subproblems

This is where the actual optimization comes in. If our problem has overlapping subproblems, that means that we are calling the same function with the exact same inputs multiple times. So we’re doing repetitive work for no reason. If we were to cache (or “memoize”) the results, we would be able to save a lot of time.

If we meet these two criteria, then we know that we can optimize our solution using dynamic programming.

## 3. Identify the Subproblems

If we find that we are able to use dynamic programming, the next step is to clearly identify the subproblems. Defining the subproblem in plain English is going to make it much easier for us to understand everything that is going on.

To approach this step, we are going to specifically look at our recursive code and see what recursive calls are being made. We then want to define in plain English what the actual meaning of that recursive call is.

For example, if we are computing the nth Fibonacci number, we have 2 recursive calls, fib(n-1) and fib(n-2). To define these in plain English, the function simply returns the nth Fibonacci number. Pretty simple.

Once we’ve identified what the subproblems are, we can also memoize our recursive solution to make it more efficient. All this means is that we are going to add an array or HashMap that stores all of the values that we’ve previously computed.

Each time we make a function call, we will look in our array to see if a result has already been computed for the current inputs. If so, then we can return it without actually computing anything. If not, we compute it and then save it into our array.

For full code and example problems, download Dynamic Programming for Interviews .

## 4. Turn Around the Solution

When doing dynamic programming, we really have two different options:

See examples of exactly how to do this in my free ebook, Dynamic Programming for Interviews .

## Next Steps : Where to Learn More About Dynamic Programming

Want to learn more about dynamic programming? Check out these online courses:

- Intro To Dynamic Programming – Coding Interview Preparation (Udemy): Specifically designed to help you gain foundational knowledge for your software engineering coding interview
- Dynamic Programming – I (Udemy): Also intro-level and geared toward coding interview basics
- Master the Art of Dynamic Programming (Udemy): In-depth theory and practice of dynamic programming
- Learn Dynamic Programming Using Python (Udemy): Hones in specifically on dynamic programming in the Python programming language
- Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming (Coursera): A course offered by Stanford about dynamic programming and other algorithm-related topics
- Dynamic Programming: Applications in Machine Learning and Genomics (edX): Learn about two interesting applications of dynamic programming that meld science and technology, from UC San Diego

## DAA Tutorial

## Help Others, Please Share

## Learn Latest Tutorials

## Preparation

## Trending Technologies

## B.Tech / MCA

## Javatpoint Services

- Website Designing
- Website Development
- Java Development
- PHP Development
- Graphic Designing
- Digital Marketing
- On Page and Off Page SEO
- Content Development
- Corporate Training
- Classroom and Online Training

## Training For College Campus

## Dynamic Programming: An Approach to Solving Computing Problems

## Dynamic programming

More From Artturi Jalli: Python Cheat Sheet: A Handy Guide to Python

## What Types of Problems Can Dynamic Programming Solve?

There are two conditions that need to be satisfied to use dynamic programming:

## What Are Overlapping Subproblems?

There are two different ways of storing the solutions to the overlapping subproblems:

## What Is Memoization?

## What Is Tabulation?

Again, the examples below should make this easier to understand.

## What Is Optimal Substructure Property?

The shortest path from the Start node to the Goal node is through nodes three and four.

## Dynamic Programming Example: Calculating Fibonacci Numbers

Due to the recursion, this function runs in exponential time.

This makes this function actually run in linear time instead of exponential time.

More in Software Engineering: Glob Module in Python: Explained

## How to Solve Problems Using Dynamic Programming

## Great Companies Need Great People. That's Where We Come In.

## DoubleAS's blog

How to solve/approach a DP problem?

At first, I'm sorry for asking this question, you may find it stupid but I need help! :(

## How to Solve Any Dynamic Programming Problem

Consistently get the right solution with the fast method.

Pramp Blog | Coding Interview & Job Search Resources for Developers

But it doesn’t have to be that way.

## What Is Dynamic Programming?

First and foremost, what is dynamic programming?

## The FAST Method

This is why I developed the FAST method for solving dynamic programming problems.

The FAST method is a repeatable process that you can follow every time to find an optimal solution to any dynamic programming problem.

## Find the first solution

## Analyze the solution

1 + 2 + 4 + … + 2^n-1 = ²⁰ + ²¹ + ²² + … + 2^n-1 = O(2^n).

With these characteristics, we know we can use dynamic programming.

## Identify the subproblems

## Turn around the solution

Dynamic programming doesn’t have to be hard or scary. By following the FAST method, you can consistently get the optimal solution to any dynamic programming problem as long as you can get a brute force solution.

Knowing the theory isn’t sufficient, however.

## Top Dynamic Programming Questions in Coding Interviews

## What is the knapsack problem, and how can it be solved using dynamic programming?

An example of this in Java would look something like this:

## What is the longest common subsequence problem, and how can it be solved using dynamic programming?

Here is an example of how this approach can be implemented in Java:

## How do you solve the traveling salesperson problem using dynamic programming?

To fill in the entries in this array, we can use the following recursive algorithm:

## Practice Makes Perfect

To see you off, check out this software engineering interview example from our friends at Exponent :

## IMAGES

## VIDEO

## COMMENTS

The six steps of problem solving involve problem definition, problem analysis, developing possible solutions, selecting a solution, implementing the solution and evaluating the outcome. Problem solving models are used to address issues that...

Maytag washers are reliable and durable machines, but like any appliance, they can experience problems from time to time. Fortunately, many of the most common issues can be solved quickly and easily. Here’s a look at how to troubleshoot som...

Having a dishwasher is a great convenience, but when it stops working properly, it can be a major inconvenience. Bosch dishwashers are known for their reliability and durability, but they can still experience problems from time to time.

Sample DP Problem · Step 1: How to recognize a Dynamic Programming problem · Step 2: Identify problem variables · Step 3: Clearly express the

Identify if it is a Dynamic programming problem. · Decide a state expression with the Least parameters. · Formulate state and transition

In this video, we go over five steps that you can use as a framework to solve dynamic programming problems. You will see how these steps are

A comprehensive and exhaustive guide to answering ANY DP problem that may come your way. Let me know if you have any questions :) ARTICLE:

How to Solve Dynamic Programming Problems Using the Fast Method · 1. Find the First Solution · 2. Analyze the First Solution · 3. Identify the

Steps to solve any Dynamic Programming Problem · Step 1: Recognize a DP problem · Step 2: Identify problem variables · Step 3: Clearly express the recurrence

In the case of recursion, repeated calls are made for the same sub-problem, but we can optimize this problem with the help of dynamic programming. The idea

The first step to solving a problem using dynamic programming is to identify it as a dynamic programming problem. If you can validate that the

2) Look at the constraints, the constraints give you a good idea about the dimension of the dp. For example : 1<=n<=500, 1<=k<=n so you can see that dp[n][k] is

To get the basic idea behind solving DP problems, go to HackerRank and in algorithms domain, select dynamic programming, and solve all the problems in the easy

To solve the LCS problem using dynamic programming, we can create a two-dimensional array that represents the characters in the two strings. The