dynamic problem solving is

Forgot password? New user? Sign up

Existing user? Log in

Dynamic Programming

Already have an account? Log in here.

• Karleigh Moore
• Norbert Madarász

Dynamic programming refers to a problem-solving approach, in which we precompute and store simpler, similar subproblems, in order to build up the solution to a complex problem. It is similar to recursion , in which calculating the base cases allows us to inductively determine the final value. This bottom-up approach works well when the new value depends only on previously calculated values.

An important property of a problem that is being solved through dynamic programming is that it should have overlapping subproblems. This is what distinguishes DP from divide and conquer in which storing the simpler values isn't necessary.

To show how powerful the technique can be, here are some of the most famous problems commonly approached through dynamic programming:

• Backpack Problem : Given a set of treasures with known values and weights, which of them should you pick to maximize your profit whilst not damaging your backpack which has a fixed capacity?
• Egg Dropping : What is the best way to drop \(n\) eggs from an \(m\)-floored building to figure out the lowest height from which the eggs when dropped crack?
• Longest Common Subsequence : Given two sequences, which is the longest subsequence common to both of them?
• Subset Sum Problem : Given a set and a value \(n,\) is there a subset the sum of whose elements is \(n?\)
• Fibonacci Numbers : Is there a better way to compute Fibonacci numbers than plain recursion?

In a contest environment, dynamic programming almost always comes up (and often in a surprising way, no matter how familiar the contestant is with it).

Motivational Example: Change of Coins

Recursion with memoization, bidimensional dynamic programming: example, example: maximum paths.

What is the minimum number of coins of values \(v_1,v_2, v_3, \ldots, v_n\) required to amount a total of \(V?\) You may use a denomination more than once.

Optimal Substructure

The most important aspect of this problem that encourages us to solve this through dynamic programming is that it can be simplified to smaller subproblems.

Let \(f(N)\) represent the minimum number of coins required for a value of \(N\).

Visualize \(f(N)\) as a stack of coins. What is the coin at the top of the stack? It could be any of \(v_1,v_2, v_3, \ldots, v_n\). In case it were \(v_1\), the rest of the stack would amount to \(N-v_1;\) or if it were \(v_2\), the rest of the stack would amount to \(N-v_2\), and so on.

How do we decide which is it? Sure enough, we do not know yet. We need to see which of them minimizes the number of coins required.

Going by the above argument, we could state the problem as follows:

\[f(V) = \min \Big( \big\{ 1 + f(V - v_1), 1 + f(V-v_2), \ldots, 1 + f(V-v_n) \big \} \Big). \]

Because the coin at the top of the stack also counts as one coin, and then we can look at the rest.

Overlapping Subproblems

It is easy to see that the subproblems could be overlapping.

For example, if we are trying to make a stack of $11 using $1, $2, and $5, our look-up pattern would be like this: \[\begin{align} f(11) &= \min \Big( \big\{ 1+f(10),\ 1+ f(9),\ 1 + f(6) \big\} \Big) \\ &= \min \Big ( \big \{ 1+ \min {\small \left ( \{ 1 + f(9), 1+ f(8), 1+ f(5) \} \right )},\ 1+ f(9),\ 1 + f(6) \big \} \Big ). \end{align} \] Clearly enough, we'll need to use the value of \(f(9)\) several times.

One of the most important aspects of optimizing our algorithms is that we do not recompute these values. To do this, we compute and store all the values of \(f\) from 1 onwards for potential future use.

The recursion has to bottom out somewhere, in other words, at a known value from which it can start.

For this problem, we need to take care of two things:

Zero : It is clear enough that \(f(0) = 0\) since we do not require any coins at all to make a stack amounting to 0.

Negative and Unreachable Values : One way of dealing with such values is to mark them with a sentinel value so that our code deals with them in a special way. A good choice of a sentinel is \(\infty\), since the minimum value between a reachable value and \(\infty\) could never be infinity.

The Algorithm

Let's sum up the ideas and see how we could implement this as an actual algorithm:

We have claimed that naive recursion is a bad way to solve problems with overlapping subproblems. Why is that? Mainly because of all the recomputations involved.

Another way to avoid this problem is to compute the data first time and store it as we go, in a top-down fashion.

Let's look at how one could potentially solve the previous coin change problem in the memoization way. 1 2 3 4 5 6 7 8 9 10 11 12 def coinsChange ( V , v ): memo = {} def Change ( V ): if V in memo : return memo [ V ] if V == 0 : return 0 if V < 0 : return float ( "inf" ) memo [ V ] = min ([ 1 + Change ( V - vi ) for vi in v ]) return memo [ V ] return Change ( V )

Dynamic Programming vs Recursion with Caching

There are \(k\) types of brackets each with its own opening bracket and closing bracket. We assume that the first pair is denoted by the numbers 1 and \(k+1,\) the second by 2 and \(k+2,\) and so on. Thus the opening brackets are denoted by \(1, 2, \ldots, k,\) and the corresponding closing brackets are denoted by \(k+1, k+2, \ldots, 2k,\) respectively.

Some sequences with elements from \(1, 2, \ldots, 2k\) form well-bracketed sequences while others don't. A sequence is well-bracketed if we can match or pair up opening brackets of the same type in such a way that the following holds:

• Every bracket is paired up.
• In each matched pair, the opening bracket occurs before the closing bracket.
• For a matched pair, any other matched pair lies either completely between them or outside them.

In this problem, you are given a sequence of brackets of length \(N\): \(B[1], \ldots, B[N]\), where each \(B[i]\) is one of the brackets. You are also given an array of Values: \(V[1],\ldots, V[N] \).

Among all the subsequences in the Values array, such that the corresponding bracket subsequence in the B Array is a well-bracketed sequence, you need to find the maximum sum.

Task: Solve the above problem for this input.

Input Format

One line, which contains \((2\times N + 2)\) space separate integers. The first integer denotes \(N.\) The next integer is \(k.\) The next \(N\) integers are \(V[1],..., V[N].\) The last \(N\) integers are \(B[1],..., B[N].\)

Constraints

• \(1 \leq k \leq 7\)
• \(-10^6 \leq V[i] \leq 10^6\), for all \(i\)
• \(1 \leq B[i] \leq 2k\), for all \(i\)

Illustrated Examples

For the examples discussed here, let us assume that \(k = 2\). The sequence 1, 1, 3 is not well-bracketed as one of the two 1's cannot be paired. The sequence 3, 1, 3, 1 is not well-bracketed as there is no way to match the second 1 to a closing bracket occurring after it. The sequence 1, 2, 3, 4 is not well-bracketed as the matched pair 2, 4 is neither completely between the matched pair 1, 3 nor completely outside of it. That is, the matched pairs cannot overlap. The sequence 1, 2, 4, 3, 1, 3 is well-bracketed. We match the first 1 with the first 3, the 2 with the 4, and the second 1 with the second 3, satisfying all the 3 conditions. If you rewrite these sequences using [, {, ], } instead of 1, 2, 3, 4 respectively, this will be quite clear.

Suppose \(N = 6, k = 3,\) and the values of \(V\) and \(B\) are as follows: Then, the brackets in positions 1, 3 form a well-bracketed sequence (1, 4) and the sum of the values in these positions is 2 (4 + (-2) =2). The brackets in positions 1, 3, 4, 5 form a well-bracketed sequence (1, 4, 2, 5) and the sum of the values in these positions is 4. Finally, the brackets in positions 2, 4, 5, 6 form a well-bracketed sequence (3, 2, 5, 6) and the sum of the values in these positions is 13. The sum of the values in positions 1, 2, 5, 6 is 16 but the brackets in these positions (1, 3, 5, 6) do not form a well-bracketed sequence. You can check the best sum from positions whose brackets form a well-bracketed sequence is 13.

We'll try to solve this problem with the help of a dynamic program, in which the state , or the parameters that describe the problem, consist of two variables.

First, we set up a two-dimensional array dp[start][end] where each entry solves the indicated problem for the part of the sequence between start and end inclusive.

We'll try to think what happens when we run across a new end value, and need to solve the new problem in terms of the previously solved subproblems. Here are all the possibilities:

• When end <= start , there are no valid subsequences.
• When b[end] <= k , i.e, the last entry is an open bracket, no valid subsequence can end with it. Effectively, the result is the same if we hadn't included the last entry at all.
• When b[end] > k , i.e, the last entry is a closing bracket, one has to find the best match for it, or simply ignore it, whichever maximizes the sum.

Can you use these ideas to solve the problem?

Very often, dynamic programming helps solve problems that ask us to find the most profitable (or least costly) path in an implicit graph setting. Let us try to illustrate this with an example.

You are supposed to start at the top of a number triangle and chose your passage all the way down by selecting between the numbers below you to the immediate left or right. Your goal is to maximize the sum of the elements lying in your path. For example, in the triangle below, the red path maximizes the sum.

To see the optimal substructures and the overlapping subproblems , notice that everytime we make a move from the top to the bottom right or the bottom left, we are still left with smaller number triangle, much like this:

We could break each of the sub-problems in a similar way until we reach an edge-case at the bottom:

In this case, the solution is a + max(b,c) .

A bottom-up dynamic programming solution is to allocate a number triangle that stores the maximum reachable sum if we were to start from that position . It is easy to compute the number triangles from the bottom row onward using the fact that the

\[\text{best from this point} = \text{this point} + \max(\text{best from the left, best from the right}).\]

Let me demonstrate this principle through the iterations. Iteration 1: 1 8 5 9 3 Iteration 2: 1 2 10 13 15 8 5 9 3 Iteration 3: 1 2 3 20 19 10 13 15 8 5 9 3 Iteration 4: 1 2 3 4 23 20 19 10 13 15 8 5 9 3 So, the effective best we could do from the top is 23, which is our answer.

Problem Loading...

Note Loading...

Set Loading...

Dynamic Programming: Definition, Methods, and Practice Questions

Dynamic programming is a useful problem-solving technique that every developer should know. While the basics are easy to learn, dynamic programming can be difficult to master. In this post, we break down the fundamentals of dynamic programming and share challenge questions to start practicing.

What is Dynamic Programming?

Dynamic programming is a problem-solving paradigm used to find a solution by breaking the larger problem into subproblems. This approach takes advantage of the fact that the optimal solution to a problem depends upon the optimal solution to its subproblems.

But dynamic programming isn’t the right approach for every problem. You can use dynamic programming to solve a problem if that problem has two characteristics:

• Overlapping Subproblems: The problem can be divided into a number of subproblems of similar type but of smaller size than the original one.
• Optimal Substructure Property: The optimal solution to the problem can be formulated from the optimal solution to its subproblems.

Dynamic Programming vs Greedy Algorithms

One helpful way to understand dynamic programming is to compare it to greedy algorithms.

A greedy algorithm is a simple, intuitive algorithm that is used in optimization problems. The algorithm makes the optimal choice at each step to find the global or overall optimal solution to the entire problem.

However, a greedy algorithm isn’t always the right approach, as it can create an inaccurate or suboptimal solution. In some situations, the largest sum or most optimal path is “hiding behind the door” of an answer that at first appears small or suboptimal.

In contrast, dynamic programming can break those decisions into components and solve for the overall optimal solution. The drawback, however, is that dynamic programming can be challenging, compared to the easier greedy algorithms .

Dynamic Programming Methods

Dynamic Programming has two methods that can be used to solve problems: top-down and bottom-up.

Top-Down Approach

A top-down (recursive) approach tries to solve the bigger problem by recursively finding the solution to smaller problems while also storing local solutions in a look-up table such that those are not computed each time. This technique is called Memo-ization.

Memoization

The advantage of the top-down approach is that it’s more intuitive to come up with solutions than the other method. However, this doesn’t always produce the most optimal solution, as it often leads to code that is slower and lengthier.

F(n) = (F(n – 1) + F(n -3), if (n >=3)

F(n) = 7, otherwise

Given n, find the n th term of the recurrence.

Top-Down Solution

int F[MAXSIZE] ;

    // set F to some unique value like -1 in this case.

    int solve(int n){

        if(n < 3){

            return 7 ;      // recurrence definition

        int &ret = F[n] ;   // cache technique

        if(ret != -1)       // absence of -1 indicate that this is already computed 

            return ret ;            // use this computed result 

        ret = solve(n-3) + solve(n-1) ;         // compute otherwise

        return F[n] = ret ;      // final return computed answer

Bottom-Up Approach

The bottom-up (iterative) approach is the opposite of the top-down approach in that you start from the smallest solution and go up to the required solution. The bottom-up approach tends to produce shorter, more optimal code. However, thinking of a bottom-up solution is less intuitive, and their base cases are often trickier than top-down base cases.

Bottom-Up Solution

        F[0] = F[1] = F[2] = 7 ;    // recurrence definition

        for(int i=3;i<=n;i++)

            F[i] = F[i-1] + F[i-3] ;    // recurrence definition

        return F[n] ;

Dynamic Programming Questions

Problem: row of numbers.

You have a row of numbers. In every turn, you can remove either the leftmost or the rightmost number and get points equal to turn_number x value of removed number. What is the maximum number of points you can get?

While you might think to use a greedy algorithm, that solution is not correct. [2, 3, 5, 1, 4] is a counter-example. This leads to the answer 2 x 1 + 3 x 2 + 4 x 3 + 1 x 4 + 5 x 5 = 49. The optimal answer in this case would be  2 x 1 + 4 x 2 + 1 x 3 + 3 x 4 + 5 x 5 = 50.

The correct solution is a dynamic programming approach.

Assume we have a function f(i, j) which gives us the optimal score of picking numbers with indices from i to j assuming the picking begins at turn number 1. Then, our answer would be f(1, n) where n is the total count of numbers.

However, notice that since we can only pick the leftmost one or the rightmost one, f(1, n) = max(g(2, n)) + val 1 , g(1, n – 1) + val j ) where g(i, j) is the optimal cost assuming picking begins at turn number 2.

A small observation: g(i, j) = f(i, j) + sum of all numbers from i to j.

Which means: f(i, j) = max(f(i, j – 1)) + sum(i, j – 1) + val j , f(i + 1, j) + sum(i + 1, j) 

Computing this relation by recursion will take an exponential amount of time because the problem of size j – i gets reduced to two instances of problem sizes j – i -1 each.

This gives the recurrence:

T(n) = 2T(n – 1)

or, T(n) = O(2 n )

Let’s try to handle this.

First of all, notice that this problem has both the required properties of a dynamic programming problem. The answer depends on the answers to smaller subproblems.

These subproblems overlap with each other: f(i, j – 1) and f(i + 1, j) both call f(i + 1, j – 1).

However, there are only O(n 2 ) different parameters of f and, therefore, only O(n 2 ) different values of f.

So, we can use memoization while calculating f. Once it has been evaluated, all subsequent calls to this state are answered using the stored value.

The complexity of this solutions is: number of states x number of transitions from each state, which is O(n 2 ) for this problem.

It is important to note that every recursion must have a base case in order to terminate. The base case here is pretty simple: f(i, i) = val i : ∀i

Problem: Max Array Sum

Difficulty Level: Medium

Given an array of integers, find the subset of non-adjacent elements with the maximum sum. Calculate the sum of that subset. It is possible that the maximum sum is 0, the case when all elements are negative.

The following subsets with more than 1 element exist. These exclude the empty subset and single element subsets which are also valid.

Subset      Sum

[-2, 3, 5]   6

[-2, 3]      1

[-2, -4]    -6

[-2, 5]      3

[1, -4]     -3

[1, 5]       6

[3, 5]       8

The maximum subset sum is 8. Note that any individual element is a subset as well.

arr = [-2, -3, -1]

In this case, it is best to choose no element: 

Function Description

Complete the maxSubsetSum function in the editor below.

maxSubsetSum has the following parameter(s):

• int arr[n]: an array of integers

– int: the maximum subset sum

Input Format

The first line contains an integer, n.

The second line contains n space-separated integers arr[i].

Constraints

• 1 <= n <= 10 5  
• -10 4 <= arr[i] <= 10 4

Sample Input 

Sample Output

Explanation

Our subsets are [2, 5, 4]. [2, 5], [2,8], [2, 4], [1, 8], [1, 4] and [5, 4] The maximum subset sum is 11 from the first subset listed.

To solve the problem with dynamic programming, work through the array, keeping track of the max at each position until you get to the last value of the array. You should start with the base cases defined before iterating through the remainder of the array.

Challenge Problem: Billboards

Difficulty Level: Advanced

Below is an advanced-level dynamic programming problem that covers topics such as dynamic programming and priority queue. Only 36.09% of developers in the HackerRank Community that have attempted this problem have succeeded. Good luck!

ADZEN is a popular advertising firm in your city that owns all n billboard locations on Main Street. The city council passed a new zoning ordinance mandating that no more than k consecutive billboards may be up at any given time. For example, if there are n = 3 billboards on Main street and k = 1, ADZEN must remove either the middle billboard, the first two billboards, the last two billboards, or the first and last billboard.

Being a for-profit company, ADZEN wants to lose as little advertising revenue as possible when removing the billboards. They want to comply with the new ordinance in such a way that the remaining billboards maximize their total revenues (i.e., the sum of revenues generated by the billboards left standing on Main street).

Given n, k, and the revenue of each of the n billboards, find and print the maximum profit that ADZEN can earn while complying with the zoning ordinance. Assume that Main street is a straight, contiguous block of n billboards that can be removed but cannot be reordered in any way.

For example, if there are n = 7 billboards, and k = 3 is the maximum number of consecutive billboards that can be active, with revenues = [5, 6, 4, 2, 10, 8, 4], then the maximum revenue that can be generated is 37: 5 + 6 + 4 + 2 + 10 + 8 + 4.

Complete the billboards function in the editor below. It should return an integer that represents the maximum revenue that can be generated under the rules.

billboards has the following parameter(s):

• k: an integer that represents the longest contiguous group of billboards allowed
• revenue: an integer array where each element represents the revenue potential for a billboard at that index

The first line contains two space-separated integers, n (the number of billboards) and k (the maximum number of billboards that can stand together on any part of the road).

Each line i of the n subsequent lines contains an integer denoting the revenue value of billboard i (where 0 <= i <= n).

• 1 <= n < 10^ 5
• 1 <= k <=n
• 0 <= revenue value of any billboard <= 2 * 10^ 9

Output Format

Print a single integer denoting the maximum profit ADZEN can earn from Main street after complying with the city’s ordinance.

Sample Input 0

Sample Output 0

Explanation 0

There are n = 6 billboards, and we must remove some of them so that no more than k = 2 billboards are immediately next to one another.

We remove the first and fourth billboards, which gives us the configuration _ 2 3 _ 6 10 and a profit of 2 + 3 + 6 + 10 + 21. As no other configuration has a profit greater than 21, we print 21 as our answer.

Sample Input 1

Sample Output 1

Explanation 1

There are n = 5 billboards, and we must remove some of them so that no more than k = 4 billboards are immediately next to one another.

We remove the first billboard, which gives us the configuration _ 2 3 4 5 and a profit of 2 + 3 +4 + 5 = 14. As no other configuration has a profit greater than 14, we print 14 as our answer.

Basics of Dynamic Programming

Dynamic Programming Interview Questions

15 Common Problem-Solving Interview Questions

HackerRank Basic Problem-Solving Skills Certification

Get started with HackerRank

Over 2,500 companies and 40% of developers worldwide use HackerRank to hire tech talent and sharpen their skills.

Recommended topics

• Coding Questions
• Interview Preparation

6 REST API Interview Questions Every Developer Should Know

LTCWM > Blog > What to learn > Skill > What Is Dynamic Programming?

What Is Dynamic Programming?

Updated on October 26th, 2023 | Sign up for learn to code tips

Table of Contents

• What Is It Used For?
• The DP Process
• Top-Down vs Bottom-Up DP
• Other Techniques
• Why Learn DP?
• How to Learn DP
• Learn DP Basics

Also referred to as DP, dynamic programming is a powerful technique for solving complex problems in computer science, engineering, and mathematics.

While it has a reputation for being intimidating, learning dynamic programming is much easier once you understand the basics.

In the simplest terms, dynamic programming is a method of solving problems by breaking them down into smaller sub-problems and reusing the solutions to these sub-problems to build up to the solution for the original problem.

This approach allows us to solve problems much more efficiently.

Dynamic programming techniques can be used to solve a wide range of problems, from finding the shortest path in a graph to solving mathematical optimization problems.

Click To Tweet

In this introduction to dynamic programming, we’ll explore dynamic programming basics like what it’s used for, steps in the process, and the different dynamic programming techniques , types, and algorithms that make it happen.

Plus, we’ll look at some real-world dynamic programming examples, compare it to other programming methods (like dynamic programming vs recursion and greedy algorithms), and share tips on how to learn dynamic programming yourself!

Disclosure: I’m a proud affiliate for some of the resources mentioned in this article. If you buy a product through my links on this page, I may get a small commission for referring you. Thanks!

Dynamic programming is a technique used in computer science and mathematics to solve problems efficiently. It helps you avoid having to solve the same problem over and over again.

🎮 Think about it like playing a video game .

In a video game, you often have to solve small problems to progress to the next level. Sometimes you encounter a problem that you’ve already solved before—so instead of going through the whole process again, you use what you learned from the last time to solve it faster.

Dynamic programming is similar. It helps you find the solution to a big problem by breaking it down into smaller, easier-to-solve problems.

You’ll solve those problems first, then take what you’ve learned from designing those solutions and apply that knowledge to solve the bigger one.

This way, you don’t have to start from scratch, and the original problem feels less insurmountable.

🌟 As this tweet explains : “It’s like having a time machine for your code; it helps you travel back to the simpler version of a problem to solve it more efficiently.”

🌟 This Redditor also has a good way of explaining what dynamic programming is: “Say I put a bunch of matches down on the table, and ask you to count them. After a few moments you say ‘12,’ then I add another match and say ‘How many are there now?’ You wouldn’t have to count them again to tell me there are 13. You already knew there were 12, and I’ve added one more. DP is this. Each individual subtask is ‘counting a match,’ and you are memorizing the previous result to get the next result, in this case, 12 matches, to count to 13 matches.”

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.

Dynamic programming vs dynamic programming languages

You might assume that a dynamic programming language is just a coding language used for DP. However, while dynamic programming and dynamic programming languages share the term “dynamic,” they are actually not directly related to each other.

Dynamic programming , as you’ve just learned, is a CS/mathematical optimization technique.

Dynamic programming languages are coding languages (like JavaScript and Python ) that allow for the modification of a program’s structure while it is running.

Don’t get confused wondering what the connection is: as far as tech concepts go, they’re not in the same category.

☝️ Back to top

What Is Dynamic Programming Used For?

Dynamic programming is commonly used for solving optimization problems, where the goal is to find the best possible solution given certain constraints.

This obviously becomes useful in a wide range of applications, such as:

• 🧮 Combinatorial mathematics: DP is used for optimization problems such as the traveling salesman problem or the knapsack problem .
• 🧬 Bioinformatics: DP can help align sequences of DNA or protein, where the goal is to find the optimal match between two sequences.
• 📅 Management & operations: Dynamic programming can be leveraged to help ops teams and managers allocate resources efficiently (eg in scheduling).
• 👁️ Computer vision and image processing: It can be used in applications to solve problems such as image segmentation and pattern recognition.
• 🤖 Natural language processing applications: DP can assist with processes like speech recognition and machine translation, to find the optimal solution for problems including sequence alignment and language modeling.

Steps in the Dynamic Programming Process

When you boil down dynamic programming basics to their simplest forms, it doesn’t seem so difficult! There are essentially just five steps: 

• Identify sub-problems: The first step is to identify the smaller sub-problems that make up the larger problem.
• Store solutions to sub-problems: Create an array or matrix to store the solutions to each sub-problem.
• Solve sub-problems: Solve each sub-problem, one at a time, and store that solution in the array or matrix.
• Use stored solutions: Use the stored solutions to build up to the solution for the original problem.
• Optimize the solution: Finally, optimize the solution by removing any redundant computations and ensuring that it is as efficient as possible.

➡️ Learn more about the steps in the dynamic programming process in this post .

Top-Down vs Bottom-Up Dynamic Programming

Bottom-up and top-down dynamic programming are two different ways to solve problems using programmers DP.

Think of them as two different ways to put together a puzzle.

🖼️ In top-down dynamic programming (also known as “memoization”), the algorithm starts by solving the original problem and then recursively breaks it down into smaller sub-problems. You then solve each small piece, one at a time, until the entire puzzle is solved. If you compare it to a jigsaw puzzle, it’s like looking at the box as you put it together.

🧩 Bottom-up dynamic programming (also called “tabulation”) is like starting with the small puzzle pieces and putting them together, piece by piece, until you have the big picture. You start by solving the smallest, easiest sub-problems first, and then use that information to solve bigger and bigger problems, until you’ve solved the whole thing.

Both top-down and bottom-up dynamic programming can be useful, depending on the problem you’re trying to solve. The choice between the two often depends on the size of the problem and how well it can be broken down into smaller parts.

Dynamic Programming Examples: 4 Problems You Can Solve with DP

Let’s look at four specific dynamic programming examples to see how DP can be put into practice to solve CS and mathematical problems!

1. Longest Common Subsequence

This algorithm is used to find the longest sequence of characters that are common to two or more strings.

For example, if you have two strings “ABCD” and “ACDF”, the longest common subsequence is “ACD”.

Breaking it down into sub-problems with dynamic programming helps you solve the LCS problem much more efficiently.

2. Fibonacci Sequence

Fibonacci is a famous sequence of numbers, where each number is the sum of the two previous numbers. The sequence starts with 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.

To find the nth Fibonacci number, you can use dynamic programming to store the solutions to the sub-problems (e.g. 0+1, 1+2) and build up to the solution for the nth number.

3. Floyd-Warshall algorithm

Used to find the shortest paths between all pairs of vertices in a weighted graph. The algorithm works by breaking the problem down into smaller sub-problems and storing the solutions to these sub-problems so they can be reused later.

When applied to the Floyd-Warshall algorithm, dynamic programming techniques allow you to solve the problem more efficiently and avoid redundant computations by reusing solutions to sub-problems.

4. Bellman Ford algorithm

Used to find the shortest path between a source vertex and all other vertices in a weighted graph. The algorithm works by relaxing the edges of the graph in a specific order and updating the distances between the vertices until the optimal solution is found. 

The Bellman-Ford algorithm uses dynamic programming by breaking the problem down into smaller sub-problems and updating the solution for each sub-problem in each iteration of the algorithm.

The algorithm stores the solution for each sub-problem in an array and uses this information to ultimately generate the solution for the original problem.

Dynamic Programming vs Recursion, Greedy Algorithms, & Static Languages

To understand dynamic programming better, it can be helpful to compare and contrast it with other techniques.

Let’s look at recursion, the greedy algorithm vs dynamic programming, and whether there’s such a thing as “static vs dynamic programming.”

Dynamic programming vs recursion

What are some of the similarities and differences in dynamic programming vs recursion?

In computer programming, recursion is when a function calls itself.

Instead of writing a long list of steps to solve a problem, you break the problem down into smaller parts, and have the function solve each smaller part one at a time, until the problem is fully solved.

Sound similar to dynamic programming? That’s because it is similar in a few key ways: 👇

• Both dynamic programming and recursion involve breaking down a problem into smaller sub-problems.
• Both techniques can involve solving the sub-problems recursively (applying the same algorithm to each sub-problem until it’s able to return a value).
• Both techniques can be used to solve problems that would otherwise be difficult or impossible to solve with other methods.

So, let’s highlight a few of the important differences: 👇

• Dynamic programming involves storing the solutions to sub-problems in memory and reusing them later, while recursion does not. This can make DP more efficient.
• They are typically used for different purposes. DP is often used for optimization problems (where the goal is to find the best solution among a set of possible solutions). Recursion is more commonly used for searching or traversal problems (where the goal is to explore a problem in a systematic way and find multiple paths).
• Recursion can use up a lot of memory if it creates too many function calls, potentially causing a stack overflow error. Dynamic programming, on the other hand, is designed to minimize the number of computations needed to reach a solution. 

Whether dynamic programming or recursion is “better” depends on the specific problem being solved. In general, it’s a good idea to consider both techniques and choose the one that is best suited to the problem at hand.

​​Greedy algorithm vs dynamic programming 

Greedy algorithms are yet another problem-solving technique that involves breaking problems down into sub-problems. However, the key difference in greedy algorithm vs dynamic programming concepts lies in how it finds solutions. 

A greedy algorithm doesn’t consider the past or future—it simply wants instant gratification. At each step, the algorithm selects the best option available to it at that point in time, without considering previous sub-problems or the overall solution.

Dynamic programming is much more well-rounded. It reuses the knowledge from prior solutions as it builds towards the larger solution.

A greedy algorithm:

• Makes locally optimal choices at each step in the hope of finding a global optimum
• Can’t always guarantee the optimal solution
• Doesn’t revisit previously solved sub-problems
• May be faster than dynamic programming algorithms for some problems

Dynamic programming:

• Solves problems by breaking them down into smaller sub-problems, solving each sub-problem once, and storing the results to avoid redundant calculations
• Can guarantee the optimal solution for a wide range of problems
• May be slower than greedy algorithms for some problems

Ultimately, if speed is your #1 concern, you might decide to use a greedy algorithm. If you want the confidence that you’re getting the best solution, DP is a better choice.

Dynamic vs static programming

Earlier, we explained that dynamic programming and dynamic programming languages are distinct concepts with different meanings and applications. Similarly, “static programming” isn’t really a thing, but “static programming languages” are.

Since this isn’t actually related to DP the computer science technique, let’s just quickly cover static vs dynamic programming languages on a high level!

When you’re working with a static programming language (like C, C++, Java , and Pascal), you’re essentially writing a set of instructions that don’t change, no matter what inputs you have.

It’s like following a recipe to bake a cake. You have all the ingredients and steps laid out in front of you, and you follow them exactly as written to get the same result every time.

When you write a program with a dynamic programming language , it can adjust and change the way it solves a problem based on the input it receives.

Continuing with our kitchen example, it’s more like cooking by experimenting and adjusting as you go. Instead of following a set recipe, you make changes and adapt based on what you learn as you cook.

Dynamic programming languages include Python , JavaScript , Ruby , and PHP .

When choosing whether to use a static or dynamic programming language for a project, programmers have to weigh considerations like performance, reliability, maintainability, ease of development, and scalability.

Why Learn Dynamic Programming?

If all of this information is hard to wrap your head around at first, it might feel hard to work up the motivation necessary for learning dynamic programming.

To help with the motivation aspect, what are some of the benefits for you if you learn it?

Learning dynamic programming can help you:

• Improve your problem-solving skills: Dynamic programming is a powerful technique for solving complex problems. Learning it can help you become a better problem-solver. 
• Work more efficiently: By breaking down a problem into smaller sub-problems and reusing the solutions to these sub-problems, dynamic programming can reduce the amount of work required to solve the original problem.
• Advance your career: Dynamic programming is widely used in computer science and engineering. Having a strong understanding of it can be beneficial in many careers, such as software development, data analysis , and artificial intelligence .
• Challenge your brain: Learning dynamic programming concepts and skills can be a mentally challenging and rewarding experience. The process of breaking down a problem into smaller sub-problems, solving each sub-problem, and building up to the solution for the original problem can be both intellectually stimulating and satisfying.

Even just familiarizing yourself with dynamic programming basics can be helpful—you don’t have to be an expert right away.

How to Learn Dynamic Programming

If you’re interested in getting a more detailed introduction to dynamic programming, here’s how to pursue further learning!

1. Start with the basics

Begin by studying the basics of algorithms and data structures , including arrays, matrices, and graphs. A strong understanding of these concepts will be essential for understanding dynamic programming.

2. Study examples of dynamic programming problems and solutions

Go through dynamic programming examples like the ones mentioned above—finding the longest common subsequence, computing Fibonacci numbers, and solving the knapsack problem.

This will help you understand how dynamic programming is used to solve real problems and give you hands-on practice.

3. Watch tutorials and take online courses

One of the best things you can do to teach yourself any new skill, of course, is to learn from the experts!

Watch online tutorials and take courses on dynamic programming. This will give you a deeper understanding of dynamic programming patterns and help you learn how to solve dynamic programming problems (from the simple to the complex).

Some of our favorite resources to learn dynamic programming include:

• Master the Art of Dynamic Programming on Udemy: Teaches you how to solve any dynamic programming problem, step by step. 
• Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming on Coursera: Covers ​​greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).
• Tushar Roy’s playlist on YouTube : It walks you through a ton of dynamic programming problems. Great for visual learners.

4. Practice, practice, practice

Finally, practice as much as you can. The more you practice, the better you will become at using dynamic programming to solve problems.

Take It Slow & Steady to Learn Dynamic Programming Basics

Learning dynamic programming takes time and practice, so be patient and persistent. With dedication and effort, you can become an expert in this powerful problem-solving technique. 

Start with free videos and articles, move on to courses, and start looking for ways to use dynamic programming in your day-to-day—you’ll be a pro in no time.

Dynamic Programming 101 | Types, Examples, and Use-Cases

Say you're planning a road trip across the country. You've got a list of cities, but you can't decide on the best route. You want to complete the trip without wasting time driving back and forth. Here's how you could plan your trip in a better way:

Kishan Pandey

Dynamic programming is one of the finest ways to solve a class of problems with sub-problems. Did that sound difficult to understand? Dive in to learn all about it with clear concepts and examples.

Dynamic programming (often abbreviated as DP) is a method for solving complex problems by breaking them down into simpler, smaller, more manageable parts. The results are saved, and the subproblems are optimized to obtain the best solution. The results are saved, and the subproblems are optimized to obtain the best solution. That sounds similar to so many other things, right? Well, let's start with an example.

Let's say you're planning a road trip across the country. You've got a list of cities you want to visit, but you can't decide on the best route. You want to visit all the cities without wasting too much time driving back and forth.

Here's how you could plan your trip in a better way:

Break the problem into smaller subproblems: The subproblems in this case are the routes from one city to another. You need to determine the time or distance between each pair of cities.

Solve each subproblem and store the solution : You can use a mapping app to find the shortest route (in time or distance) between each pair of cities. You then store this information for later use.

Use the solutions of the subproblems to solve the original problem : Now, using the information you've gathered and stored, you can construct the shortest possible route that visits all the cities. You start from your home city and then go to the nearest city. From there, you go to the nearest city that you haven't visited yet, and so on.

This is just a simple example of how dynamic programming works, but it gives you an idea of the process: breaking a complex problem down into simpler parts, solving each part, storing the solutions, and then combining the solutions to solve the original problem.

Table of Contents:

What is dynamic programming

When to use dynamic programming

The fibonacci sequence

Step-by-step approach to DP

Types of dynamic programming

Which approach to choose when

What is Dynamic Programming

Thought first by Richard Bellman in the 1950s, Dynamic Programming (DP) is a problem-solving technique used in computer science and mathematics to solve complex larger problems by breaking them down into simpler, smaller overlapping subproblems. The key idea is solving each subproblem once and storing the results to avoid redundant calculations. DP is particularly useful for problems where the solution can be expressed recursively and the same subproblem appears multiple times.

It's like tackling a giant jigsaw puzzle by piecing together smaller sections first.

Simply put, DP stores the solution to each of these smaller parts to avoid doing the same work over and over again(like you would store the shortest routes between cities in the first example). So, with dynamic programming, you're not just working harder, you're working smarter!

When to use Dynamic Programming?

So, how do you know when to use dynamic programming? There are two key hallmarks of a problem that's ripe for a DP approach:

• Overlapping Subproblems: Dynamic Programming thrives on identifying and solving overlapping subproblems. These are smaller subproblems within a larger problem that are solved independently but repeatedly. By solving and storing the results of these subproblems, we avoid redundant work and speed up the overall solution. Let’s go back to the road trip example. Imagine that the travel from City A to City B is common in several different routes. Now, instead of calculating the distance between the two cities every single time we’re mapping different routes, we can store the distance and reuse it whenever needed. This is an example of overlapping subproblems.
• Optimal Substructure: Another crucial concept is the optimal substructure property. It means that the optimal solution to a larger problem can be generated from the optimal solutions of its smaller subproblems. This property allows us to break down complex problems into simpler ones and build the solution iteratively. Let's say we've figured out the shortest route from City A to City B, and the shortest route from City B to City C. The shortest route from City A to City C via City B would be the combination of these two shortest routes. So, by knowing the optimal solutions (shortest routes) to the subproblems, we can determine the optimal solution to the original problem. That's an optimal substructure.

Practical Application: The Fibonacci Sequence

To really get a grip on dynamic programming, let's explore a classic example: The Fibonacci sequence.

It is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1.

Fibonacci Series: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34…and so on.

Mathematically, we could write each term using the formula:

F(n) = F(n-1) + F(n-2),

With the base values F(0) = 0, and F(1) = 1. And we’ll follow the above relationship to calculate the other numbers. For example, F(6) is the sum of F(4) and F(5), which is equal to 8.

Let’s look at the diagram for better understanding.

Suppose we’ve to calculate F(10). Going by the formula, F(10) should be the sum of F(8) and F(9). Similarly, F(9) would also be the sum of the subproblems F(7) and F(8). As you can see, F(8) is an overlapping subproblem here.

In the above example, if we calculate the F(8) in the right subtree, then it would result in a increased usage of resources and reduce the overall performance.

The better solution would be to store the results of the already computed subproblems in an array. First, we’ll solve F(6) and F(7) which will give us the solution to F(8) and we’ll store that solution in an array and so on. Now when we calculate F(9), we already have the solutions to F(7) and F(8) stored in an array and we can just reuse them. F(10) can be solved using the solutions of F(8) and F(9), both of which are already stored in an array.

Similarly, at each iteration we store the solutions so we don’t have to solve them again and again. This is the main attribute of dynamic programming.

If you try to compute this sequence with a straightforward recursive function, you'll end up doing a lot of unnecessary work. ( Want to understand recursion from scratch? )

Here's a simple Python implementation using DP to calculate a Fibonacci sequence:

Step-by-Step Approach to DP

Let's explore how to implement dynamic programming step-by-step:

• Grasp the Problem
• Find the Overlapping Subproblems
• Compute and Store Solutions
• Construct the Solution to the Main Problem

Types of Dynamic Programming

Dynamic programming is divided into two main approaches: top-down (memoization) and bottom-up (tabulation). Both of these methods help in solving complex problems more efficiently by storing and reusing solutions of overlapping subproblems, but they differ in the way they go about it.

Let's dive into these two approaches:

Top-Down DP (Memoization)

In the top-down approach, also known as memoization, we start with the original problem and break it down into subproblems. Think of it like starting at the top of a tree and working your way down to the leaves.

Here, problems are broken into smaller ones, and the answers are reused when needed. With every step, larger, more complex problems become tinier, less complicated, and, thus, faster to solve, and the results of each subproblem are stored in a data structure like a dictionary or array to avoid recalculating them. The ‘memoization’ (a key technique in DP where you store and retrieve previously computed values) process is equivalent to adding the recursion (any function that calls itself again and again) and caching steps.

Some parts can be reused for the same problem and solved when requested, making them easier to debug. However, this approach results in more memory in the call stack being occupied, which can result in a reduction in overall performance and stack overflow.

Let's revisit the Fibonacci sequence example:

Here, memo is a dictionary that stores the previously computed numbers. Before we compute a new Fibonacci number, we first check if it's already in memo. If it is, we just return the stored value. If it's not, we compute it, store it in memo, and then return it.

Bottom-Up DP (Tabulation)

The bottom-up approach, also known as tabulation, takes the opposite direction. This approach solves problems by breaking them up into smaller ones, solving the problem with the smallest mathematical value, and then working up to the problem with the biggest value. Solutions to its subproblems are compiled in a way that falls and loops back on itself. Users can opt to rewrite the problem by initially solving the smaller subproblems and then carrying those solutions for solving the larger subproblems.

Here, we fill up a table (hence the name "tabulation") in a manner that uses the previously filled values in the table. This way, by the time we come to the problem at hand, we already have the solutions to the subproblems we need.

Let's use the Fibonacci sequence again to illustrate the bottom-up approach:

In this case, fib_table is an array that stores the Fibonacci numbers in order. We start by filling in the first two numbers (0 and 1), and then we iteratively compute the rest from these initial numbers.

In contrast to the top-down approach, the bottom-up approach relies on eliminating recursion functions. There is no stack overflow, and memory space is saved with reduced timing complexity, making it more efficient and preferred when the order of solving subproblems is not critical.

Which approach to choose?

Both top-down and bottom-up dynamic programming can be useful, and your choice depends on the problem at hand and the specific requirements of your program.

The top-down approach might be easier to understand because it follows the natural logic of the problem, but it can involve a lot of recursion and may have a larger memory footprint due to the call stack.

On the other hand, the bottom-up approach can be more efficient because it avoids recursion and uses a loop instead, but it might require a better understanding of the problem to build the solution iteratively.

What are the signs of DP suitability?

Identifying whether a problem is suitable for solving with dynamic programming (DP) involves recognizing certain signs or characteristics that suggest DP could be an effective approach. Here are some common signs that indicate a problem might be a good fit for dynamic programming:

• Overlapping Subproblems: A problem that can be broken down into smaller subproblems that are solved independently, and the same subproblems encountered multiple times strongly indicates DP suitability.
• Optimal Substructure: Problems that exhibit optimal substructure can often be solved using DP. This means that the optimal solution for a larger problem can be constructed from the optimal solutions of its smaller subproblems.
• Recursive Nature: Problems that can be naturally expressed using recursion are often well-suited for DP.
• Memoization Opportunities: If you notice that you can improve a recursive algorithm by memoizing (caching) intermediate results, DP might be a good fit.
• Sequential Dependencies: Problems where the solution depends on the results of previous steps or stages are often candidates for DP. DP is particularly useful when solving problems involving sequences, such as strings, arrays, or graphs.
• Optimization or Counting: DP is often applied to optimization problems (maximizing or minimizing a value) or counting problems (finding the number of possible solutions).
• Recursive Backtracking Inefficiency: If you encounter a recursive backtracking algorithm that is slow due to repeated calculations, this is a clear indication that DP might be a better approach.
• Subproblem Independence: Some problems have subproblems that are entirely independent of each other. In such cases, DP can be applied to solve each subproblem in parallel or any order, making it an efficient choice.
• Limited Set of Choices: Problems where the number of choices at each step is limited and doesn't grow exponentially can often be tackled with DP. DP can explore all possible choices without leading to an impractical number of computations.

Final Thoughts

Dynamic programming is a little like magic: It turns a daunting problem into a series of manageable tasks, making the impossible possible. But unlike a magic trick, the method behind dynamic programming is logical and grounded in sound reasoning.

Sure, getting the hang of it might take some time. You'll need to practice spotting overlapping subproblems and constructing optimal solutions. But once you've mastered these skills, you'll be able to tackle a wide range of problems with newfound efficiency.

Dynamic programming is a useful but advanced skill to learn if one is a programmer or DevOps engineer, particularly if you specialize in Python. It makes complex algorithmic problems easy to digest and its versatility makes it a must-have in the repertoire of every DevOps learning kit. Remember, the journey of a thousand miles begins with a single step – or in our case, a single subproblem.

Cheers and Happy Coding!

FAQs on Dynamic Programming

When should i use dynamic programming.

Use Dynamic Programming when you encounter problems with overlapping subproblems and optimal substructure. Common applications include algorithms for optimization, like finding the shortest path, maximizing profit, or minimizing cost.

Are there different types of Dynamic Programming?

Yes, Dynamic Programming can be categorized into two main types: Memoization (Top-down) and Tabulation (Bottom-up). The choice between them depends on the specific problem and your coding preferences.

Learn more:

The Art of Debugging: Mastering the Bug Hunt, One Error at a Time

Introduction to Object-Oriented Programming

How Software is Developed? A Step-By-Step Guide

Array vs Linked List [When to use What]

7-Step Approach to Solve Any Coding Problem

Our Courses

Practice-Based Learning Tracks, Supercharged By A.I.

Dynamic Programming: An Approach to Solving Computing Problems

Sometimes in computer science, you will run into problems. You can divide these into subproblems, which can, in turn, be divided into smaller subproblems. If the smaller subproblems overlap, then you can save the result in memory for future reference. This way, you don’t need to compute the same result multiple times, thus increasing the efficiency of the program substantially. This way of solving these problems is referred to as dynamic programming.

In this article, you will learn what dynamic programming is. I will also show how to compute Fibonacci numbers, which is a simple problem that dynamic programming can solve. I will compare the dynamic programming solutions to the naive solution that uses recursion. These examples are written in Python syntax. Finally, I’ll also give some general pointers to keep in mind when attempting to solve problems using dynamic programming

Dynamic programming

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

What Types of Problems Can Dynamic Programming Solve?

Dynamic programming is typically a way to optimize solutions to certain problems that use recursion. If a recursive solution to a problem has to compute solutions for subproblems with the same inputs repeatedly, then you can optimize it through dynamic programming. As mentioned earlier, in this case, you would simply save the result of the computation for use later if and when it’s needed. This optimization can reduce the time complexity of an algorithm from exponential time to polynomial time. This means that the number of computations n scales like a polynomial expression instead of scaling like an exponential expression as n increases. In general, polynomial expressions grow much slower than exponential expressions.

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

• Overlapping subproblems
• Optimal substructure property

What Are Overlapping Subproblems?

I alluded to the overlapping subproblems condition earlier. It simply means that when solving the problem in question, the solutions for the same subproblems are repeatedly necessary. In this case, the solutions to these subproblems can be stored for later use to skip recomputation.

Another way to think about this condition is to turn it upside down. If there are no overlapping subproblems, then there’s no point in saving the solutions for the subproblems, and you can’t use dynamic programming.

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

• Memoization (top-down)
• Tabulation (bottom-up)

What Is Memoization?

The memoization approach to dynamic programming is very similar to the naive recursion approach, with only a small change. The difference is that we use a lookup table to store solutions to the subproblems, and then use this table to check whether that solution already exists.

If the solution for a certain subproblem already exists in the lookup table, then that solution is returned from the lookup table. If it does not, then it needs to be computed (through recursion) and added to the lookup table.

For the sake of clarity, let’s define a solution for a subproblem in our dynamic programming problem to be DP[X] ., with DP[N] being the desired solution and DP[0] being the base solution. In the memoization approach, the program starts from DP[N] and asks for the solutions from which DP[N] can be reached (these should be subproblems of lower order DP[n<N]) . Then, from these states, the same process is repeated recursively, until reaching the base solution DP[0] .

If this feels a little too abstract, don’t worry. The examples introduced later in this article should clarify what I mean.

Memoization is known as a top-down approach to dynamic programming since the program will start from the desired, last (top) state and work its way down recursively.

What Is Tabulation?

The tabulation approach to dynamic programming works in a reverse manner compared to the memoization approach. The program will start from the base (or bottom) solution for the subproblem and work its way up, solving the subproblems one by one until reaching the desired solution.

In terms of solutions to subproblems, the tabulation approach starts from the base solution DP[0] and then calculates DP[1], DP[2], … DP[N] until reaching the desired solution for the subproblem DP[N] . Since we started from the base solution DP[0] and worked towards the desired solution DP[N] , the tabulation approach is also known as a bottom-up approach.

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

What Is Optimal Substructure Property?

If the optimal solution to a problem can be obtained using the optimal solution to its subproblems, then the problem is said to have optimal substructure property .

As an example, let’s consider the problem of finding the shortest path between ‘Start’ and ‘Goal’ nodes in the graph below. The nodes are connected to other nodes via edges, and the distance between two connected nodes is marked with a number next to the edge.

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

This problem clearly has optimal substructure property. Since the shortest path from the Start node to the Goal node goes through Node Four, it clearly follows that this path is a combination of the shortest path from the Start node to Node Four and the shortest path from Node Four to the Goal node.

Many problems do not have optimal substructure property. For example, the problem of finding the longest path (with no cycles) between the Start node and the Goal node in the above graph doesn’t. Here’s how you can see this:

The longest path is: Start - Node Three - Node Two - Node One - Node Four - Goal. However, this does not imply that the longest path from the Start node to Node Two is Start - Node Three - Node Two. The longest path from the Start node to Node Two is actually Start - Node One - Node Four - Node Three - Node Two (and Start - Node One - Node Four - Goal - Node Two, which has equal length to the first one).

Dynamic Programming Example: Calculating Fibonacci Numbers

One of the simplests examples of dynamic programming is the computation of Fibonacci numbers, which are numbers from the Fibonacci sequence. The first Fibonacci number is zero, the second is one, and the subsequent numbers are the sum of the previous two Fibonacci numbers. The 10 first Fibonacci numbers are  zero, one, one, two, three, five, eight, 13, 21, and 34.

Let’s first start with the naive, recursive solution. Here’s a Python function to calculate the nth Fibonacci number (indexing starts from zero):

From this example it is easy to see that this problem satisfies the overlapping subproblems condition since the function clearly has to calculate the previous Fibonacci numbers multiple times (when n > three). The smallest Fibonacci numbers are computed most often, when this function is called for a large n.

This problem also clearly has optimal substructure since there is only a single solution for the subproblems, which are used to compute the solution to the desired problem.

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

Let’s next look at how this could be solved using dynamic programming. Let’s start with a top-down solution using memoization. Here’s a Python function that calculates the nth Fibonacci number that implements dynamic programming through memoization:

This approach is quite similar to the recursive approach since it starts from calculating the nth Fibonacci number and, in order to calculate it, goes onto calculating the n-1st and n-2nd Fibonacci numbers. The difference is in the lookup table, where the smaller Fibonacci numbers will be saved as they are calculated, so that they do not need to be calculated again and again.

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

For the sake of an example, let’s also look at a Python function that solves the same problem in a bottom-up manner with dynamic programming using tabulation:

In this solution, the nth Fibonacci number is calculated in a bottom-up manner, starting by calculating the first Fibonacci number, then the second, third and so on until reaching the nth Fibonacci number. This function also runs in linear time.

More in Software Engineering: Glob Module in Python: Explained

How to Solve Problems Using Dynamic Programming

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 problem has overlapping subproblems and that it satisfies the optimal substructure property, you can be sure that you can solve it with dynamic programming.

The second step is to decide on a state expression. This state is the set of parameters that uniquely identifies the different subproblems.

In the Fibonacci numbers example, the parameter identifying the state would just be the serial number of a certain Fibonacci number.

There can be more than one parameter identifying a state. You should always use as few parameters as possible, however.

The third — and probably hardest — step in solving problems using dynamic programming is formulating the relation between the different states.

In the Fibonacci number case this is simple, however, since the nth Fibonacci number is the sum of the n-1st and n-2nd Fibonacci numbers. So F[n] = F[n-1] + F[n-2].

The fourth step is to implement memoization or tabulation for the states that you decided upon, using the relation you discovered between the states. This means simply saving the state (or in other words the solution to a certain subproblem) so it can be recovered from memory without recomputation when it is needed again. This should be fairly simple, if you did steps one to three well

Built In’s expert contributor network publishes thoughtful, solutions-oriented stories written by innovative tech professionals. It is the tech industry’s definitive destination for sharing compelling, first-person accounts of problem-solving on the road to innovation.

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

For enquiries call:

+1-469-442-0620

• Programming

A Comprehensive Guide to Dynamic Programming

Home Blog Programming A Comprehensive Guide to Dynamic Programming

Embarking on the dynamic programming journey involves breaking down a tough algorithmic problem into smaller pieces, saving their results, and then making them work better to find a complete solution. The main focus is usually on figuring out the biggest and smallest values within the algorithmic query. In this article, I dig into the details of dynamic programming, taking a close look at how it works. Using examples, I'll guide you through the step-by-step process, showing how dynamic programming is a powerful and efficient way to solve problems. By working smartly through smaller problems, this method leads to the best solutions in a systematic way.   

Overall, dynamic programming is a strong and effective approach to problem-solving in the world of algorithms, making complex challenges more manageable and solutions more accessible.    

What is Dynamic Programming

Dynamic programming is a technique of breaking down a problem into smaller problems, solving each sub-problems once, storing the solutions of these sub-problems, and eventually finding a solution to the original problem.  

We break down a big problem into smaller problems. Typically, the smaller problems are similar to the parent problem only difference being the scale. Thus, these sub-problems can also be divided further smaller sub-problems until we achieve problems that cannot be further divided. You can imagine we have a tree of a problem and their sub-problems. We start with solving the “leaf” level problems and then move on to their “parent” problems and so on. We save the results as we solve sub-problems for future reference. Thereby avoiding working on the same sub-problem if encountered again.  

This approach is like the divide and conquers algorithm where a problem is divided into sub-problems and recursively solving sub-problems and combining their solution to find the solution to the real problem.

Dynamic Programming Characteristics

It is important to know when to use dynamic programming algorithms. There are two major characteristics to identify whether dynamic programming is the right fit.  

1. Optimal Substructure   

The problem should have optimal substructure properties. It means that the optimal solution can be evaluated from the optimal solutions of its sub-problems. This will also help you define the base case of the recursive algorithm.  

Consider an example of the Fibonacci series. We define the n th  number as the sum of the previous 2 numbers.  

2. Fib(n) = Fib(n-1) + Fib(n-2)    

We can see that a problem of size “ n ” can be broken down into sub-problems of size “ n-1 ” and “ n-2 ”. We also know solutions of base cases, i.e.,  f(0)  as 0 and  f(1)  1.   as 1.    

3. Overlapping subproblems  

The other necessary property is overlapping sub-problems. A problem is said to have overlapping sub-problem properties if the sub-problems can be seen recursively visiting the same sub-problems. In such cases, we can improve the performance of an algorithm by storing the results of each sub-problem once it is calculated.

As seen above, in the case of Fibonacci dynamic programming numbers tree representation, several sub-problems like fib(4), fib(3), fib(2), and so on can be seen occurring multiple times.  

Note that both optimal substructure and overlapping sub-problems dynamic programming patterns are required for a problem to be a dynamic programming problem.  

Example of Dynamic Programming

One can easily find a lot of dynamic programming examples on the internet. We will discuss one of the popular examples here.  

Consider a rod of length  n  inches and an array of prices that includes prices of all pieces of size smaller than  n . We need to determine the maximum sum of money we can make by cutting up the rod and selling the pieces.   

length   | 1   2   3  

--------------------  

price    | 1   5   8  

With the above set of prices, if the length of the rod is 4, we can get a maximum value of 10 by cutting the rod into two pieces of length 2.  

The image below shows that the problem can be broken down into smaller sub-problems, which can further be broken down into smaller sub-problems. We also know the solution of the base case, i.e., the price of length 0 is 0.  This depicts the property of optimal substructure.  

We can also see that the same sub-problems (highlighted in color) are being repeated. This confirms that the problem has an overlapping sub-problem characteristic.

To solve this problem, we divide the rod of length  n  into two parts:  i  and  n-i.  We repeat this process for the second part and divide  n-i  further in the same fashion. We store the maximum profit for each length  i  of the rod. In the end, the maximum of all values will be the expected value.  

Here is a code snippet in java. This gives you an idea about the implementation of  dynamic programming in java.  

Dynamic Programming Techniques

There are two dynamic programming methods of implementation.  

Top-Down Approach

This approach solves the bigger problem by recursively solving smaller sub-problems. As we solve the sub-problems, we store the result for later use. This way, we don’t need to solve the same sub-problem more than once. This method of saving the intermediate results is called Memoization (not memorization).  

Bottom-Up Approach

The bottom-up method is an iterative version of the top-down approach. This approach starts with the smallest and works upwards to the largest sub-problems. Thus when solving a particular sub-problem, we already have results of smaller dependent sub-problems. The results are stored in an  n -dimensional ( n=>0 ) table. Thus, you can imagine when we arrive at the original problem, we have solved all its sub-problems. Now we just use the result set to find the best solution. This method is called Tabulation.  

Which one is better?

• The top-down approach is typically recursive. It has the overhead of recursive calls and therefore is slower than the bottom-up approach.  
• One might find the top-down approach easier to implement because we use an array of some sort of lookup table to store results during recursion. While for the bottom-up approach we need to define the order of iteration and define an  n -dimensional table for storing results.  
• The top-down approach might also run into stack overflow conditions in the case of a very deep recursion tree.  

Dynamic Programming Algorithms

Greedy algorithms.

Greedy algorithms are problem-solving strategies that make locally optimal choices at each step with the hope of finding a global optimum. In a greedy algorithm, decisions are made based on the current best option without revisiting or reconsidering previous choices. While this approach doesn't guarantee the absolute best solution, it often produces acceptable results and is commonly used for optimization problems like minimum spanning trees, coin change, and scheduling.

Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a dynamic programming technique used for finding the shortest paths between all pairs of vertices in a weighted graph. It considers all possible paths and systematically updates the shortest path distances between every pair of vertices until the optimal solution is reached. This algorithm is particularly useful for scenarios where the graph may contain negative weight edges.

Bellman Ford Algorithm

The Bellman-Ford algorithm is employed for finding the shortest path from a source vertex to all other vertices in a weighted graph, even in the presence of edges with negative weights. This algorithm iteratively relaxes edges, adjusting distance estimates until the optimal solution is achieved, or a negative weight cycle is detected. The Bellman-Ford algorithm is valuable for scenarios where graphs may contain negative weight edges, which can pose challenges for other algorithms like Dijkstra's.

Steps to Solve Dynamic Programming Problems

We will understand the steps with a popular example: The coin change problem with dynamic programming.   

You are given coins of varying denominations and asked to pay a certain amount with the fewest coins possible. How do you write a program for this?  

1.  Identify the sub-problem and write it down in words  

Start by defining the problem statement in programmable constructs.  

There is an array of coins with varying denominations and an integer sum representing the total amount of money. We need to return the fewest coins (values from the array) required to make up that sum. If that sum cannot be accumulated with given denominations, return -1.  We will assume that infinite coins are available for the given denominations.  

Now we break down the problem into smaller variations. Start with assuming real values for which you know the solution. For example, if the sum is 40 and the denominations are {1, 5, 10, 25}. If you work it out on paper, you can see that you need three coins: 25, 10, and 5. There are other possibilities, but incorrect, solutions like {5, 5, 5, 5, 5, 5, 5, 5}, {10, 10, 10, 5, 5} and so on.  

To find the sub-problem, we can see that the sum of two numbers can express any amount. These numbers can be further expressed as the sum of two numbers.   

The smallest number, 1, is present in the denomination. So any number  n  can be expressed as 1 + ( n  – 1).    

2.  Sub-problem expressed as Mathematical recurrence  

In the above case, the sub-problem can be expressed as. case, sub-problem can be expressed as.  

min_coins ( 40 ) =  min_coins ( 40  — c) +  1  

Where c is the number of the allowed denomination.  

This equation can be made generic by replacing 40 with  n .  

min_coins (n) =  min_coins (n — c) +  1    

3.  Define  memoization  array strategy to fill it  

We know that the problem has characteristics of overlapping sub-problems. We can use the memoization technique to cache the results of sub-problems for later use.  

In this case, we can simply use an array of lengths as the given amount. We will store the minimum coins required for a particular sub-amount, an index of the same value. This makes it easier to fetch the result when required.  

4.  Coding the solution  

While coding the algorithm, one can start with the initialization of the array (or cache) if required. Next, one should set the base case. Each problem can be solved in multiple ways using the dynamic programming approach. You need to think about which one suits you.  

Below is the dynamic programming python implementation of the above-discussed problem. However, dynamic programming algorithms can be implemented in any language. If you want to use python,  Python Programming certification  is a great starting point.  

       For  coin-in coins:    

        Else :    

        else:    

Advantages of Dynamic Programming

• Dynamic programming can be used to obtain local as well as the total optimal solution.  
• Dynamic programming algorithms are generally compact code pieces as they are based on recursive functions.  
• The linear and non-linear problem, both kind of problems can be solved using dynamic programming.  
• Dynamic programming algorithms are easy to debug.  

Disadvantages of Dynamic Programming

• Dynamic programming uses recursion, which requires more memory in the call stack, and leads to a stack overflow condition in the runtime.  
• It takes memory to store the solutions of each sub-problem. There is no guarantee that the stored value will be used later in execution.  
• High memory usage might lead to degraded performance. It depends on the dynamic programming algorithm and the programming language. For java, you can do  Java certification  to be able to use java efficiently.  

In summary, my journey through the Dynamic Programming Algorithm has been marked by enlightening discoveries and practical applications. By integrating real-life case studies and examples, I aim to underscore the substantial impact of DP on effective problem-solving. Reflecting on my roles as an enthusiast, expert, and practitioner, I am assured that Dynamic Programming will persist as a cornerstone in algorithmic optimization. It provides a resilient framework for addressing intricate challenges, offering both a strategic approach and tangible solutions. As the significance of DP continues to unfold, it stands poised to remain an essential tool, shaping the landscape of efficient problem-solving in the evolving realms of algorithms and optimization..  

Frequently Asked Questions (FAQs)

There are numerous applications of dynamic programming in real life. Finding the shortest path between the source and multiple destinations. Git merge uses DP coding to find the longest common subsequence. There are other applications like image processing, optimal inventory management, production optimization, genetic algorithms, and matrix multiplication dynamic programming; the list is endless.

Recursion is calling a function within itself. Sub-problems might have to be solved multiple times when a problem is solved using recursion. At the same time, Dynamic programming is a technique where you store the result of the previous calculation to avoid calculating the same once again.

Algorithms that are aimed at solving optimization problems use a dynamic programming approach. Examples of dynamic programming algorithms are string algorithms like the longest common subsequence, longest increasing subsequence, and the longest palindromic substring. Optimizing the order for chain matrix multiplication. The Bellman-Ford algorithm for finding the shortest distance in a graph.

Paresh Patil

Paresh is a Software developer by profession with a major experience in big data and backend development. Along with writing quality code and implementing robust system design, he takes a keen interest in generating maximum value for end-user. He loves "chai" and trekking.

Avail your free 1:1 mentorship session.

Something went wrong

Upcoming Programming Batches & Dates

Dynamic Programming: Examples, Common Problems, and Solutions

Dynamic programming problems can catch you off-guard in an interview or exam. Check out the most common problems and the solutions here.

There’s no doubt that dynamic programming problems can be very intimidating in a coding interview. Even when you may know that a problem needs to be solved using a dynamic programming method, it’s a challenge to be able to come up with a working solution in a limited time frame.

The best way to be good at dynamic programming problems is to go through as many of them as you can. While you don’t necessarily need to memorize the solution to every problem, it’s good to have an idea of how to go about implementing one.

What Is Dynamic Programming?

Simply put, dynamic programming is an optimization method for recursive algorithms, most of which are used to solve computing or mathematical problems.

You can also call it an algorithmic technique for solving an optimization problem by breaking it into simpler sub-problems. A key principle that dynamic programming is based on is that the optimal solution to a problem depends on the solutions to its sub-problems.

Wherever we see a recursive solution that has repeated calls for the same inputs, we can optimize it using dynamic programming. The idea is to simply store the results of subproblems so that we do not have to re-compute them when needed later.

Dynamically programmed solutions have a polynomial complexity which assures a much faster running time than other techniques like recursion or backtracking. In most cases, dynamic programming reduces time complexities, also known as big-O , from exponential to polynomial.

Now that you have a good idea of what dynamic programming is, it’s time to check out a few common problems and their solutions.

Dynamic Programming Problems

1. knapsack problem.

Problem Statement

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight doesn’t exceed a given limit and the total value is as large as possible.

You’re given two integer arrays values[0..n-1] and weights[0..n-1] which represent values and weights associated with n items respectively. Also given is an integer W which represents the knapsack capacity.

Here we’re solving the 0/1 knapsack problem, which means that we can choose to either add an item or exclude it.

• Create a two-dimensional array with n+1 rows and w+1 columns. A row number n denotes the set of items from 1 to i , and a column number w denotes the maximum carrying capacity of the bag.
• The numeric value at [i][j] denotes the total value of items up till i in a bag that can carry a maximum weight of j.
• At every coordinate [i][j] in the array, pick the maximum value that we can obtain without item i , or the maximum value that we can obtain with item i ---whichever is larger.
• The maximum obtainable value by including item i is the sum of item i itself and the maximum value that can be obtained with the remaining capacity of the knapsack.
• Perform this step until you find the maximum value for the W th row.

2. Coin Change Problem

Suppose you’re given an array of numbers that represent the values of each coin. Given a specific amount, find the minimum number of coins that are needed to make that amount.

• Initialize an array of size n+1 , where n is the amount. Initialize the value of every index i in the array to be equal to the amount. This denotes the maximum number of coins (using coins of denomination 1) required to make up that amount.
• Since there is no denomination for 0, initialise the base case where array[0] = 0 .
• For every other index i , we compare the value in it (which is initially set to n+1 ) with the value array[i-k] +1 , where k is less than i . This essentially checks the entire array up till i-1 to find the minimum possible number of coins we can use.
• If the value at any array[i-k] + 1 is lesser than the existing value at array[i] , replace the value at array[i] with the one at array[i-k] +1 .

3. Fibonacci

The Fibonacci Series is a sequence of integers where the next integer in the series is the sum of the previous two.

It’s defined by the following recursive relation: F(0) = 0, F(n) = F(n-1) + F(n-2) , where F(n) is the nth term. In this problem, we have to generate all the numbers in a Fibonacci sequence up till a given nth term.

• First, use a recursive approach to implement the given recurrence relation.
• Recursively solving this problem entails breaking down F(n) into F(n-1) + F(n-2) , and then calling the function with F(n-1) and F(n+2) as parameters. We do this until the base cases where n = 0 , or n = 1 are reached.
• Now, we use a technique called memoization. Store the results of all function calls in an array. This will ensure that for every n, F(n) only needs to be calculated once.
• For any subsequent calculations, its value can simply be retrieved from the array in constant time.

4. Longest Increasing Subsequence

Find the length of the longest increasing subsequence inside a given array. The longest increasing subsequence is a subsequence within an array of numbers with an increasing order. The numbers within the subsequence have to be unique and in ascending order.

Also, the items of the sequence do not need to be consecutive.

• Start with a recursive approach where you calculate the value of the longest increasing subsequence of every possible subarray from index zero to index i, where i is lesser than or equal to the size of the array.
• To turn this method into a dynamic one, create an array to store the value for every subsequence. Initialise all the values of this array to 0.
• Every index i of this array corresponds to the length of the longest increasing subsequence for a subarray of size i .
• Now, for every recursive call of findLIS(arr, n) , check the n th index of the array. If this value is 0, then calculate the value using the method in the first step and store it at the n th index.
• Finally, return the maximum value from the array. This is the length of the longest increasing subsequence of a given size n .

Solutions to Dynamic Programming Problems

Now that you’ve gone through some of the most popular dynamic programming problems, it’s time to try implementing the solutions by yourself. If you’re stuck, you can always come back and refer to the algorithm section for each problem above.

Given how popular techniques such as recursion and dynamic programming are today, it won’t hurt to check out some popular platforms where you can learn such concepts and hone your coding skills . While you might not run into these problems on a daily basis, you'll surely encounter them in a technical interview.

Naturally, having the know-how of common problems is bound to pay dividends when you go for your next interview. So open up your favourite IDE , and get started!

Learn Dynamic Programming Techniques in Java

Dynamic programming is a powerful technique that has been a cornerstone in the world of algorithms and computer science. It's a method that breaks down problems into smaller, more manageable sub-problems, solving each one only once and storing their solutions in case they're needed again. This approach is particularly useful for optimization problems, where you seek the best solution amongst a set of feasible solutions.

We just posted a course on the freeCodeCamp.org YouTube channel that will teach you Dynamic Programming techniques with Java.

Alvin Zablan created this course. It provides a deep dive into dynamic programming and teaches a lot of key algorithms.

What is Dynamic Programming?

Dynamic programming is a method for solving complex problems by breaking them down into simpler sub-problems. It is a way to solve problems by using solutions to smaller instances of the same problem.

The key idea behind dynamic programming is quite simple. In general, to solve a problem, you solve some sub-problems. Dynamic programming is used when the sub-problems are not independent, i.e., when sub-problems share sub-sub-problems. In this context, divide and conquer algorithms do more work than necessary, repeatedly solving the common sub-sub-problems. Dynamic programming algorithms remember past results and use them to find new results.

When is Dynamic Programming Used?

Dynamic programming is often used in optimization problems where we have to find the best solution among a set of feasible solutions. It's particularly useful when a problem has overlapping sub-problems. Instead of computing solutions to these sub-problems repeatedly, dynamic programming suggests solving each of these sub-problems just once, saving their solutions, and returning the saved solution when the same sub-problem is encountered again.

Dynamic Programming in Coding Interviews

Dynamic programming is a favorite topic in coding interviews. Interviewers love to test the understanding, analytical skills, and problem-solving abilities of candidates using dynamic programming problems. It's not just about knowing the technique but also about understanding when and how to use it. Mastering dynamic programming can give you a significant edge in coding interviews.

Course Breakdown

Here are the sections covered in the course:

• fib : Dive into the Fibonacci sequence, a classic example to kickstart your dynamic programming journey.
• tribonacci : Explore the tribonacci sequence, a variation of the Fibonacci sequence.
• sum possible : Learn to determine if a sum is possible with given numbers.
• min change : Find out the minimum change required from a set of denominations.
• count paths : Count the number of paths in a grid.
• max path sum : Calculate the maximum path sum in a grid.
• non adjacent sum : Find the maximum sum without adding adjacent numbers.
• summing squares : Understand the concept of summing squares in dynamic programming.
• counting change : Learn different ways to count change using given denominations.

Whether you're a beginner looking to understand the basics of dynamic programming or an advanced coder aiming to brush up your skills, this course has something for everyone.

You can watch the full course on the freeCodeCamp.org YouTube channel (3-hour watch).

I'm a teacher and developer with freeCodeCamp.org. I run the freeCodeCamp.org YouTube channel.

If you read this far, thank the author to show them you care. Say Thanks

Learn to code for free. freeCodeCamp's open source curriculum has helped more than 40,000 people get jobs as developers. Get started

Code With C

The Way to Programming

• C Tutorials
• Java Tutorials
• Python Tutorials
• PHP Tutorials
• Java Projects

Dynamic Programming: Strategies for Solving Complex Problems Efficiently

Dynamic Programming Demystified 🚀

Hey there, fellow tech enthusiasts! 🤖 Today, let’s delve into the fascinating world of Dynamic Programming 🌟. Don’t be scared off by the jargon; I’m here to break it down with a sprinkle of humor and a dollop of enthusiasm! So, grab your virtual seat and let’s dive right in! 💻

Understanding Dynamic Programming

So, what in the world is Dynamic Programming ? 🤔 Imagine you have this colossal problem to solve, and it’s so complex that you feel like pulling your hair out! Dynamic Programming swoops in like a superhero, offering you a strategy to break down this mammoth task into bite-sized, manageable chunks. Voila! Problem solved! 💪

Definition of Dynamic Programming

Dynamic Programming is like the master chef in the kitchen of algorithms . It’s a methodical way of solving complex problems by breaking them down into simpler subproblems. 🍳 Each subproblem’s solution is stored to avoid redundant calculations, making the overall process more efficient. Efficiency for the win! 🎉

Importance of Dynamic Programming

Picture this: You’re at a buffet, and you want to sample every dish. Dynamic Programming allows you to do just that in the realm of algorithms – optimize your solutions and tackle even the most intricate problems with finesse. It’s like having a secret recipe book for cracking challenging puzzles in record time! 🍽️

Basic Principles of Dynamic Programming

Let’s talk about the fundamental rules that make Dynamic Programming the rockstar of problem-solving techniques! 🌟

• Overlapping Subproblems : It’s like finding money in the pockets of your old jeans. Dynamic Programming identifies these recurring subproblems and saves their solutions for later use, eliminating unnecessary work. It’s all about efficiency, baby! 💸
• Optimal Substructure : This principle is like building a sturdy LEGO tower. Each piece (subproblem) fits perfectly to create the optimal solution . Dynamic Programming ensures that each subproblem’s solution contributes to the overall best answer. It’s all about that solid foundation! 🏗️

Strategies for Applying Dynamic Programming

Now that we’ve got the basics under our belt, let’s explore the two dynamic strategies that make the magic happen! 🎩✨

• Top-down Approach : Imagine you’re skydiving from the top. This approach starts with the main problem and recursively breaks it down into subproblems. It’s adventurous, exhilarating, and definitely keeps you on your toes! 🪂
• Bottom-up Approach : Ever built a tower from the ground up? That’s the bottom-up approach. You start with the smallest subproblems, gradually solving larger ones until you conquer the main problem like a champ. It’s a steady climb to success! 🗼

Applications of Dynamic Programming

Dynamic Programming isn’t just a fancy term; it’s the powerhouse behind some incredible real-world applications! 🌐 Let’s take a peek at a couple of them:

• Fibonacci Sequence : Ah, the Fibonacci sequence, nature’s favorite mathematical marvel ! Dynamic Programming nimbly calculates Fibonacci numbers faster than you can say “Golden Ratio.” It’s all about those efficient number-crunching skills! 🔢
• Shortest Path Algorithms : Navigating through a maze? Dynamic Programming has your back! It’s the GPS guiding you through the shortest route with speed and precision. Say goodbye to taking the long, scenic route! 🗺️

Challenges and Tips for Mastering Dynamic Programming

Ah, every hero has their kryptonite, right? Let’s uncover some challenges in mastering Dynamic Programming and how to conquer them like a pro! 🦸‍♂️

• Identifying Optimal Substructure : Sometimes the forest (complex problem) is so dense that you can’t see the trees (optimal substructure). Mastering Dynamic Programming involves honing your detective skills to spot these crucial patterns. Sherlock, who? 🕵️
• Handling State Transitions efficiently : It’s like switching gears in a Formula 1 race. Efficiently transitioning between states is key to zipping through problems with ease. Rev up those mental engines and zoom past any hurdles! 🏎️

Overall, Mastering Dynamic Programming Like a Pro! 🚀

So, there you have it, folks! Dynamic Programming, the unsung hero of problem-solving, ready to tackle any challenge with finesse. Remember, practice makes perfect, and with a dash of determination and a sprinkle of creativity, you’ll be mastering Dynamic Programming like a seasoned pro in no time! 💪

Thanks for tuning in, and remember: Keep coding, keep smiling, and embrace the dynamic journey ahead! 🌟

Stay Dynamically Awesome, Techies! 🚀👩‍💻

In closing, thanks a ton for joining me on this Dynamic Programming rollercoaster! 🎢 Keep shining bright and solving those tech puzzles like a boss! See you in the next coding adventure! ✨

Program Code – Dynamic Programming: Strategies for Solving Complex Problems Efficiently

Code Output: The 10th Fibonacci number is: 55

Code Explanation:

In the given dynamic programming example , we solve for the nth Fibonacci number, a popular problem showcasing the elegance and efficiency of the dynamic programming approach. The recursive nature of the Fibonacci sequence, where each number is the sum of the two preceding ones (excluding the first two numbers which are both considered as 1), makes it an ideal candidate for dynamic programming, particularly memoization.

The code defines a fibonacci function that takes two arguments: n , the position in the Fibonacci sequence whose value we want to find, and memo , a dictionary used as a cache to store the results of the Fibonacci numbers we’ve already computed.

At the function’s core, we employ a base case for when n is less than or equal to 2. For these cases, we simply return 1, as the first two Fibonacci numbers by definition are 1.

The true power and efficiency lie in the subsequent lines. Before plunging headlong into a recursive frenzy, we first check if our current n is in the memo . If it’s not, this means we haven’t computed it yet, and then we proceed to perform the recursive operations to calculate fibonacci(n-1) and fibonacci(n-2) . Crucially, we then store this computed value in memo[n] . This storage step is what saves us from the redundant work if we encounter the same n value again in our computations.

In essence, any subsequent calls for the same Fibonacci number won’t have to go through the recursion again; instead, they’ll directly fetch the result from our memo , dramatically reducing the time complexity from what would have been exponential in a naive recursive approach (O(2^n)) to O(n) in our dynamic programming approach.

Let’s not forget—the function concludes by returning the memoized or newly computed value of the nth Fibonacci number, giving us our desired result efficiently and elegantly. Dynamic programming, with its memoization strategy, thus transforms an otherwise computationally intensive problem into a tractable one, showcasing its power in optimizing the performance of algorithms dealing with overlapping subproblems.

Frequently Asked Questions (F&Q) on Dynamic Programming

What is dynamic programming and how does it work.

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It involves solving each subproblem only once and storing the solution to avoid redundant calculations. This approach can significantly improve the efficiency of solving problems with overlapping subproblems.

When should I use dynamic programming to solve a problem?

Dynamic programming is most useful when a problem can be broken down into overlapping subproblems, and the optimal solution to the problem can be constructed from optimal solutions to its subproblems. It is commonly used in optimization problems, such as finding the shortest path or maximizing profit.

What are the key characteristics of problems that are suitable for dynamic programming?

Problems suitable for dynamic programming usually exhibit two key characteristics: optimal substructure and overlapping subproblems. Optimal substructure means that the optimal solution to the problem can be constructed from the optimal solutions to its subproblems. Overlapping subproblems refer to the fact that the same subproblems are solved multiple times in a recursive algorithm .

Can you provide an example of a problem that can be solved using dynamic programming?

One classic example of a problem solved using dynamic programming is the Fibonacci sequence. By storing the results of subproblems (calculating Fibonacci numbers for smaller indices), we can avoid redundant calculations and compute the nth Fibonacci number efficiently.

Are there different strategies or approaches to dynamic programming?

Yes, there are several strategies for approaching dynamic programming problems, such as top-down with memoization and bottom-up with tabulation. Top-down with memoization involves solving the problem recursively while storing the results of subproblems to avoid redundant calculations. Bottom-up with tabulation involves solving the problem iteratively, starting from the smallest subproblems and building up to the desired solution.

What are some common pitfalls to avoid when using dynamic programming?

One common pitfall when using dynamic programming is not recognizing the overlapping subproblems and failing to store and reuse intermediate results. It is essential to identify the repeating subproblems to benefit from the efficiency of dynamic programming . Additionally, starting with a brute-force approach before optimizing with dynamic programming can help in understanding the problem better.

How can I improve my skills in dynamic programming?

To improve your skills in dynamic programming, practice solving a variety of problems that can be optimized using dynamic programming techniques . Online coding platforms, coding contests, and algorithmic problem-solving websites offer a wide range of problems to help you sharpen your skills. Additionally, studying different dynamic programming patterns and approaches can enhance your problem-solving abilities.

What are some resources to learn more about dynamic programming?

There are plenty of resources available to deepen your understanding of dynamic programming, including online courses, textbooks, and tutorials. Websites like LeetCode, GeeksforGeeks, and CodeSignal offer practice problems and explanations related to dynamic programming. Additionally, joining online coding communities and forums can provide valuable insights and tips from experienced programmers in the field.

You Might Also Like

Binary decision diagrams: simplifying complex decision processes, optimizing data search in binary search trees, binary search tree: structure, operations, and applications, binary tree search: navigating trees for efficient data retrieval, searching in a binary search tree: algorithms and efficiency.

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Latest Posts

Cutting-Edge Network Security Project: Distributed Event-Triggered Trust Management for Wireless Sensor Networks

Wireless Ad Hoc Network Routing Protocols Under Security Attack Project

Cutting-Edge Collaborative Network Security Project for Multi-Tenant Data Centers in Cloud Computing

Predictive Network Security Situation Project

Enhancing Network Security: Dynamic Validation Project

Privacy overview.

Sign in to your account

Username or Email Address

Remember Me

What is Dynamic Programming? Solve Complex Problems with Ease self.__wrap_b=(t,n,e)=>{e=e||document.querySelector(`[data-br="${t}"]`);let a=e.parentElement,r=R=>e.style.maxWidth=R+"px";e.style.maxWidth="";let o=a.clientWidth,c=a.clientHeight,i=o/2-.25,l=o+.5,u;if(o){for(;i+1 {self.__wrap_b(0,+e.dataset.brr,e)})).observe(a):process.env.NODE_ENV==="development"&&console.warn("The browser you are using does not support the ResizeObserver API. Please consider add polyfill for this API to avoid potential layout shifts or upgrade your browser. Read more: https://github.com/shuding/react-wrap-balancer#browser-support-information"))};self.__wrap_b(":R4mr36:",1)

What is Dynamic Programming?

Principles of dynamic programming, when to use dynamic programming, example: fibonacci numbers.

Dynamic programming is a powerful technique used in computer science, mathematics, and operations research to solve complex problems by breaking them down into simpler, overlapping subproblems. It is particularly useful for optimization problems, where the objective is to find the best solution among a set of possible solutions. Dynamic programming can be applied to a wide range of problems, including sequence alignment, shortest path routing, and resource allocation. In this blog post, we will delve into the concept of dynamic programming, explore its principles, and learn how to implement it in code. By the end of this post, you should have a solid understanding of dynamic programming and how it can help you solve complex problems with ease.

Dynamic programming is a technique used to solve problems by dividing them into simpler, overlapping subproblems and combining their solutions to construct the optimal solution. It is based on the idea of recursion, where a problem is solved by breaking it down into smaller instances of the same problem. Unlike naive recursion, however, dynamic programming stores the results of each subproblem in a data structure called a "memoization table," allowing us to avoid redundant computations.

The two main approaches to dynamic programming are top-down and bottom-up:

• Top-down (Memoization): In this approach, we start by solving the original problem and recursively break it down into smaller subproblems. Whenever we encounter a subproblem that has already been solved, we simply look up its solution in the memoization table, thus reducing the overall time complexity. This approach is also called "memoization."
• Bottom-up (Tabulation): In this approach, we iteratively build up solutions to the problem, starting from the simplest subproblems and gradually working our way up to the original problem. This method fills in the memoization table iteratively, ensuring that all required subproblem solutions are available before solving the main problem. This approach is also called "tabulation."

There are two key principles underlying dynamic programming:

• Optimal Substructure: This principle states that the optimal solution to a problem can be constructed from optimal solutions to its subproblems. This means that if we can find the best solution for each subproblem, we can use these solutions to create the optimal solution for the main problem.
• Overlapping Subproblems: This principle states that a problem can be broken down into smaller subproblems that are solved independently, and their solutions are reused multiple times. This allows us to use memoization or tabulation techniques to store the results of subproblems and avoid redundant computations, thus improving the efficiency of the algorithm.

Dynamic programming can be applied to problems that exhibit the following characteristics:

• Optimal substructure: The problem can be broken down into smaller, overlapping subproblems, and the optimal solution to the main problem can be constructed from the optimal solutions of these subproblems.
• Overlapping subproblems: The problem can be solved by solving smaller instances of the same problem, and these smaller instances are solved multiple times during the course of solving the main problem.

To illustrate the concept of dynamic programming, let's consider the classic problem of computing the Fibonacci numbers. The Fibonacci sequence is defined as follows:

• F(n) = F(n-1) + F(n-2) for n > 1

Naive Recursion

A naive recursive solution to compute the nth Fibonacci number can be implemented as follows:

In this implementation, we store the computed Fibonacci numbers in a dictionary called memo . This way, we avoid recomputing overlapping subproblems and reduce the time complexity to O(n).

Dynamic Programming: Bottom-Up Approach (Tabulation)

Now, let's implement the bottom-up approach using tabulation:

In this implementation, we iteratively fill in the table array with the Fibonacci numbers, starting with the simplest cases (F(0) and F(1)) and working our way up to F(n). This approach has a time complexity of O(n) and does not require recursion.

Q: What are the main differences between memoization and tabulation?

A: Memoization is a top-down approach that utilizes a memoization table to store the results of subproblems. It relies on recursion to break down the main problem into smaller subproblems. Tabulation, on the other hand, is a bottom-up approach that iteratively builds up solutions, starting from the simplest subproblems and working its way up to the main problem. Both methods use memoization tables to store intermediate results, but they differ in their strategies for filling in these tables.

Q: When should I use dynamic programming?

A: You should consider using dynamic programming when the problem exhibits optimal substructure and overlapping subproblems. This means that the problem can be broken down into smaller, simpler subproblems, and their solutions can be combined to construct the optimal solution to the main problem. Additionally, these subproblems should be solved multiple times during the course of solving the main problem, allowing you to benefit from memoization or tabulation techniques.

Q: Can dynamic programming be used for problems other than optimization?

A: Yes, dynamic programming can be applied to various types of problems, including counting problems, combinatorial problems, and decision-making problems. As long as a problem exhibits optimal substructure and overlapping subproblems, dynamic programming can be a useful technique for solving it efficiently.

Q: How do I choose between the top-down and bottom-up approaches?

A: The choice between top-down and bottom-up approaches depends on the problem at hand and your specific requirements. The top-down approach (memoization) is usually easier to implement, as it closely follows the problem's natural recursive structure. However, it can lead to higher memory usage due to recursion. The bottom-up approach (tabulation) may require more careful planning to build up the solutions iteratively, but it can often lead to lower memory usage and better cache performance. Consider your specific problem and constraints todetermine the most appropriate approach.

Q: Are there any limitations to dynamic programming?

A: Dynamic programming has some limitations. First, it may not be applicable to problems that do not exhibit optimal substructure and overlapping subproblems. Second, the time complexity of dynamic programming algorithms can still be quite high for some problems, especially those with large input sizes or complex memoization tables. Lastly, dynamic programming may lead to increased memory usage due to the need to store intermediate results in memoization tables.

Dynamic programming is a powerful technique that can help you solve complex problems with ease by breaking them down into simpler, overlapping subproblems. By using memoization or tabulation, dynamic programming can significantly reduce the time complexity of algorithms and improve their efficiency. Understanding the principles of dynamic programming and learning how to implement it in code can greatly enhance your problem-solving skills and expand your toolbox as a programmer or computer scientist.

We hope this blog post has provided you with a clear understanding of dynamic programming and its applications. With this knowledge, you are now better equipped to tackle a wide range of challenging problems that may have seemed daunting before.

Sharing is caring

Did you like what Mehul Mohan wrote? Thank them for their work by sharing it on social media.

No comment s so far

Curious about this topic? Continue your journey with these coding courses:

2.8k students learning

Piyush Garg

Mastering Algorithms

• Harvard Business School
• HBS Theses and Dissertations
• Communities & Collections
• By Issue Date
• FAS Department
• Quick submit
• Waiver Generator
• DASH Stories
• Accessibility
• COVID-related Research
• Terms of Use
• Privacy Policy
• By Collections
• By Departments

Show simple item record

Dynamic Problem Solving for Breakthrough Innovation: The Case of a Social Robot

Files in this item.

This item appears in the following Collection(s)

• HBS Theses and Dissertations [54]

• Interview Problems on DP
• Practice DP
• Tutorial on Dynamic Programming
• Optimal Substructure
• Overlapping Subproblem
• Memoization
• Tabulation vs Memoization
• 0/1 Knapsack
• Unbounded Knapsack
• Coin Change
• Egg Dropping Puzzle
• Matrix Chain Multiplication
• Palindrome Partitioning
• DP on Arrays
• DP with Bitmasking
• DP on Trees
• DP on Graph
• Meanings and objectives of Tabulation
• Longest Chain of Dominoes Game
• Difference between Recursion and Dynamic Programming
• Maximizing Chocolates in Grid (Chocolates Pickup II)
• Count the number of ways a person can walk, roll or jump
• Maximum Gold Coins in Broken Blocks
• Count Valid Numbers with Equal Digit Frequencies
• Program to print double sided Stair-Case Pattern
• Minimum Cost to Remove All Array Elements
• Minimize steps for Knight to collect maximum points (Knight in Geekland)
• Postmaster Letters Collection
• Is Data Structures and Algorithms Required for Android Development?
• Maximizing Readability-Coefficient for Book Printing
• Convert a Linked List to Peak list
• What should I learn first, C++ STL or DSA?
• Find a pair with difference between Values and Indices in the Array
• Find Lexicographically smallest String with Prefix Reversal
• What does Big O - O(log N) complexity mean?
• Maximum Ways to Cross the field

How Does Dynamic Programming Work?

Dynamic programming, popularly known as DP, is a method of solving problems by breaking them down into simple, overlapping subproblems and then solving each of the subproblems only once, storing the solutions to the subproblems that are solved to avoid redundant computations. This technique is useful for optimization-based problems, where the goal is to find the most optimal solution among all possible set of solutions.

Table of Content

What is Dynamic Programming?

Dynamic programming characteristics.

• Techniques to solve Dynamic Programming Problems
• Understanding Dynamic Programming With Examples

Dynamic Programming is a problem-solving technique used to solve complex problems by breaking them into smaller overlapping subproblems and solving each subproblem only once, storing the solutions to avoid redundant computations. It often involves optimal substructure and overlapping subproblems to efficiently solve problems with recursive structures.

This approach is like the divide and conquers algorithm where a problem is divided into sub-problems and recursively solving sub-problems and combining their solution to find the solution to the original problem.

Dynamic programming is a way of solving tricky problems by breaking them into smaller pieces and solving each piece just once, saving the answers to avoid doing the same work over and over.

Here are two key things to check if dynamic programming is the right tool for the job:

1. Optimal Substructure:

• The problem should have optimal substructure , meaning the best solution comes from combining optimal solutions to smaller sub-problems.
• Take the Fibonacci series as an example, where the nth number is the sum of the previous two numbers: Fib(n) = Fib(n-1) + Fib(n-2).
• This shows how a problem of size “ n ” can be broken down into sub-problems of size “ n-1 ” and “ n-2 ,” helping define the base cases of the recursive algorithm (e.g., f(0) = 0, f(1) = 1).

2. Overlapping Subproblems:

• The other essential characteristic is overlapping subproblems , where the same smaller problems occur repeatedly in a recursive manner.
• By recognizing and storing the solutions to these overlapping subproblems, algorithm performance can be significantly improved.
• In the Fibonacci dynamic programming example, the tree representation reveals that sub-problems like fib(4), fib(3), fib(2), etc., appear multiple times.
• Remember, for a problem to be a good fit for dynamic programming, it needs both optimal substructure and overlapping subproblems.

Techniques to solve Dynamic Programming Problems:

1. top-down(memoization):.

Break down the given problem in order to begin solving it. If you see that the problem has already been solved, return the saved answer. If it hasn’t been solved, solve it and save it. This is usually easy to think of and very intuitive, This is referred to as Memoization .

2. Bottom-Up(Dynamic Programming):

Analyze the problem and see in what order the subproblems are solved, and work your way up from the trivial subproblem to the given problem. This process ensures that the subproblems are solved before the main problem. This is referred to as Bottom-up Dynamic Programming .

Types of the approach of dynamic programming algorithm

Understanding Dynamic Programming With Examples:

Problem: Let’s find the Fibonacci sequence up to the nth term . A Fibonacci series is the sequence of numbers in which each number is the sum of the two preceding ones. For example, 0, 1, 1, 2, 3, and so on. Here, each number is the sum of the two preceding numbers.

Naive Approach: The basic way to find the nth Fibonacci number is to use recursion.

Below is the implementation for the above approach:

Complexity Analysis:

• Here, for every n, we are required to make a recursive call to fib(n – 1) and fib(n – 2). For fib(n – 1), we will again make the recursive call to fib(n – 2) and fib(n – 3). Similarly, for fib(n – 2), recursive calls are made on fib(n – 3) and fib(n – 4) until we reach the base case.
• During each recursive call, we perform constant work(k) (adding previous outputs to obtain the current output). We perform 2nK work at every level (where n = 0, 1, 2, …). Since n is the number of calls needed to reach 1, we are performing 2n-1k at the final level. Total work can be calculated as:
• If we draw the recursion tree of the Fibonacci recursion then we found the maximum height of the tree will be n and hence the space complexity of the Fibonacci recursion will be O(n).

Efficient approach: As it is a very terrible complexity(Exponential), thus we need to optimize it with an efficient method. ( Memoization )

Let’s look at the example below for finding the 5th Fibonacci number.

Observations:

The entire program repeats recursive calls. As in the above figure, for calculating fib(4) , we need the value of fib(3) (first recursive call over f ib(3) ), and for calculating fib(5) , we again need the value of fib(3)(second similar recursive call over fib(3) ). Both of these recursive calls are shown above in the outlining circle. Similarly, there are many others for which we are repeating the recursive calls. Recursion generally involves repeated recursive calls, which increases the program’s time complexity. By storing the output of previously encountered values (preferably in arrays, as these can be traversed and extracted most efficiently), we can overcome this problem. The next time we make a recursive call over these values, we will use their already stored outputs instead of calculating them all over again. In this way, we can improve the performance of our code. Memoization is the process of storing each recursive call’s output for later use, preventing the code from calculating it again. Way to memoize: To achieve this in our example we will simply take an answer array initialized to -1. As we make a recursive call, we will first check if the value stored in the answer array corresponding to that position is -1. The value -1 indicates that we haven’t calculated it yet and have to recursively compute it. The output must be stored in the answer array so that, next time, if the same value is encountered, it can be directly used from the answer array. Now in this process of memoization, considering the above Fibonacci numbers example, it can be observed that the total number of unique calls will be at most (n + 1) only.

Time complexity: O(n) Auxiliary Space: O(n)

Optimized approach: Following a bottom-up approach to reach the desired index. This approach of converting recursion into iteration is known as Bottom up-Dynamic programming(DP) .

Finally, what we do is recursively call each response index field and calculate its value using previously saved outputs. Recursive calls terminate via the base case, which means we are already aware of the answers which should be stored in the base case indexes. In the case of Fibonacci numbers , these indices are 0 and 1 as f(ib0) = 0 and f(ib1) = 1 . So we can directly assign these two values ​​into our answer array and then use them to calculate f(ib2), which is f(ib1) + f(ib0), and so on for each subsequent index. This can easily be done iteratively by running a loop from i = (2 to n). Finally, we get our answer at the 5th index of the array because we already know that the ith index contains the answer to the ith value. Simply, we first try to find out the dependence of the current value on previous values ​​and then use them to calculate our new value. Now, we are looking for those values which do not depend on other values, which means they are independent(base case values, since these, are the smallest problems which we are already aware of).

Dynamic programming , also known as DP , is a problem-solving technique that is very powerful. It breaks complex problems into simpler, overlapping subproblems and then, one by one, solves each problem. Memorization and tabulation are two approaches to implementing dynamic programming. Memorization , a top-bottom approach, optimises recursive solutions by storing results in a memo table. Tabulation , a bottom-up approach, builds solutions through an iterative approach and provides an efficient alternative. Both techniques enhance algorithm efficiency, as demonstrated in the Fibonacci numbers example, optimizing time and space complexities.

Please Login to comment...

• Geeks Premier League 2023
• Dynamic Programming
• Geeks Premier League
• 10 Best Tools to Convert DOC to DOCX
• How To Summarize PDF Documents Using Google Bard for Free
• Best free Android apps for Meditation and Mindfulness
• TikTok Is Paying Creators To Up Its Search Game
• 30 OOPs Interview Questions and Answers (2024)

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Course Code: AMS2027

Course Title: Dynamic Problem Solving

Competency Areas: Negotiation & Influence

Delivery Types: eLearning, Gamification, On-Site Instructor Led, Virtual Instructor Led

Related Solutions

• Conflict Resolution Professional Development Training
• Critical Thinking Professional Development Training
• Basic Elements of Root Cause Analysis Research Articles
• Agile Problem Solving Professional Development Training
• Building a Culture of Collaboration Professional Development Training
• Systems Thinking Professional Development Training
• Strategy Design and Planning Best Practice Organizational Development Consulting
• Innovation as a Mindset Professional Development Training
• Design Thinking in an Agile Environment Professional Development Training
• Entrepreneurship as a Mindset Professional Development Training

Dynamic Problem Solving

Dynamic Problem Solving offers a set of best practices and critical thinking methods to make decisions and formulate sustainable solutions. This course provides the knowledge, skills, tools, and techniques to succeed in solving a wide range of problems. It also examines critical and creative thinking in both framing and solving problems from a leadership perspective. Participants will experience a dynamic learning experience to test their new skills and apply them to real-time work scenarios.

Learning Modules 

Collaborative Decision-Making

• A Holistic Approach
• Decision Making Styles
• Problem Solving in Decision Making
• Learning to Listen, Listening to Learn

Decision Making in Action

• Getting A Clear Picture
• Decision Making Tools
• Organizing and Evaluating Data
• Making & Implementing Decisions

Critical Thinking Process

• Critical Thinking Concepts
• Problem Solving Process
• Framing & Defining the Problem
• Tools to Define the Problem

Assessing and Analyzing Data & Solutions

• Identify & Test Assumptions
• Tools for Examining the Problem
• SCAMPER – A Tool for Divergent Thinking
• Data visualization

Who Should Attend

Teams, Leaders, and Individual Contributors, seeking to enhance their skills around the daily, strategic, and complex problem/decision making process, will benefit from this program.

Engagement Options

Enterprise  – for corporate groups of eight or more participants, delivered On-Site or Live Online with options to customize your learning experience as noted below.  Contact Us to Discuss Your Unique Needs> 

• Accelerated Course = 2-learning modules delivered in a half day
• Full course = 4-learning modules delivered in one day
• Thought Leader Series = topical overview delivered in a 1-hour session
• Accelerated Course = 2-curated learning modules delivered in one 3.5-hour session
• Full Course = 4-learning modules delivered in two 3.5-hour sessions

Delivery Methods:

Open Enrollment  – for individual learners or cohorts of less than eight participants, delivered Live Online. Contact Us for Scheduling Options >

Customize your Learning Experience 

• Personalize Scenarios, Thought Leader Questions, and Exercises
• Partner via our Stewardship Engagement Model – Watch the Video 
• Select Delivery Modality and durations
• Extend Learning with  Research Articles
• Sustain Performance with  Performance Coaching
• Build  Learning Tracks  by Linking Courses & Modules
• Build your  Learning Academy
• Enhance at Desk Application through Business Simulation Training 
• Earn Select Industry Accreditations
• Whodunit – Murder Mystery – Team Building 

CONTACT US TO DISCUSS YOUR UNIQUE NEEDS>