dynamic programming and problem solving

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: 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!

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.

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

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.

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

Innovative Machine Learning Project: Neural Language-Based Port Recommendation System for Alternative Container Port Destinations Project

Cutting-Edge Machine Learning Project: Disease Gene Association Analysis Project

Cutting-Edge Deep Learning & NLP Project: Image Caption Generation

Ear-based Human Recognition Project Unveiled Using Deep Learning Technology

Innovative Natural Language Processing News Classification Project

Privacy overview.

Sign in to your account

Username or Email Address

Remember Me

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.

Follow these steps to solve any Dynamic Programming interview problem

by Nikola Otasevic

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

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

Dynamic Programming — Predictable and Preparable

One of the reasons why I personally believe that DP questions might not be the best way to test engineering ability is that they’re predictable and easy to pattern match. They allow us to filter much more for preparedness as opposed to engineering ability.

These questions typically seem pretty complex on the outside, and might give you an impression that a person who solves them is very good at algorithms. Similarly, people who may not be able to get over some mind-twisting concepts of DP might seem pretty weak in their knowledge of algorithms.

The reality is different, and the biggest factor in their performance is preparedness. So let’s make sure everyone is prepared for it. Once and for all.

7 Steps to solve a Dynamic Programming problem

In the rest of this post, I will go over a recipe that you can follow to figure out if a problem is a “DP problem”, as well as to figure out a solution to such a problem. Specifically, I will go through the following steps:

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

Sample DP Problem

For the purpose of having an example for abstractions that I am going to make, let me introduce a sample problem. In each of the sections, I will refer to the problem, but you could also read the sections independently of the problem.

Problem statement:

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

Here are the rules:

1) You’re given a flat runway with a bunch of spikes in it. The runway is represented by a boolean array which indicates if a particular (discrete) spot is clear of spikes. It is True for clear and False for not clear.

Example array representation:

2) You’re given a starting speed S. S is a non-negative integer at any given point, and it indicates how much you will move forward with the next jump.

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

4) You want to safely stop anywhere along the runway (does not need to be at the end of the array). You stop when your speed becomes 0. However, if you land on a spike at any point, your crazy bouncing ball bursts and it’s game over.

The output of your function should be a boolean indicating whether we can safely stop anywhere along the runway.

Step 1: How to recognize a Dynamic Programming problem

First, let’s make it clear that DP is essentially just an optimization technique. DP is a method for solving problems by breaking them down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. The next time the same subproblem occurs, instead of recomputing its solution, you simply look up the previously computed solution. This saves computation time at the expense of a (hopefully) modest expenditure in storage space.

Recognizing that a problem can be solved using DP is the first and often the most difficult step in solving it. What you want to ask yourself is whether your problem solution can be expressed as a function of solutions to similar smaller problems.

In the case of our example problem, given a point on the runway, a speed, and the runway ahead, we could determine the spots where we could potentially jump next. Furthermore, it seems that whether we can stop from the current point with the current speed depends only on whether we could stop from the point we choose to go to next.

That is a great thing, because by moving forward, we shorten the runway ahead and make our problem smaller. We should be able to repeat this process all the way until we get to a point where it is obvious whether we can stop.

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

Step 2: Identify problem variables

Now we have established that there is some recursive structure between our subproblems. Next, we need to express the problem in terms of the function parameters and see which of those parameters are changing.

Typically in interviews, you will have one or two changing parameters, but technically this could be any number. A classic example of a one-changing-parameter problem is “determine an n-th Fibonacci number”. Such an example for a two-changing-parameters problem is “Compute edit distance between strings”. If you’re not familiar with these problems, don’t worry about it.

A way to determine the number of changing parameters is to list examples of several subproblems and compare the parameters. Counting the number of changing parameters is valuable to determine the number of subproblems we have to solve. It’s also important in its own right in helping us strengthen the understanding of the recurrence relation from step 1.

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

• Array position (P)

One could say that the runway ahead is changing as well, but that would be redundant considering that the entire non-changing runway and the position (P) carry that information already.

Now, with these 2 changing parameters and other static parameters, we have the complete description of our sub-problems.

Identify the changing parameters and determine the number of subproblems.

Step 3: Clearly express the recurrence relation

This is an important step that many rush through in order to get into coding. Expressing the recurrence relation as clearly as possible will strengthen your problem understanding and make everything else significantly easier.

Once you figure out that the recurrence relation exists and you specify the problems in terms of parameters, this should come as a natural step. How do problems relate to each other? In other words, let’s assume that you have computed the subproblems. How would you compute the main problem?

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

Because you can adjust your speed by up to 1 before jumping to the next position, there are only 3 possible speeds, and therefore 3 spots in which we could be next.

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

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

If we can find a way to stop in any of the subproblems above, then we can also stop from (S, P). This is because we can transition from (S, P) to any of the above three options.

This is typically a fine level of understanding of the problem (plain English explanation), but you sometimes might want to express the relation mathematically as well. Let’s call a function that we’re trying to compute canStop. Then:

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

Woohoo, it seems like we have our recurrence relation!

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

Step 4: Identify the base cases

A base case is a subproblem that doesn’t depend on any other subproblem. In order to find such subproblems, you typically want to try a few examples, see how your problem simplifies into smaller subproblems, and identify at what point it cannot be simplified further.

The reason a problem cannot be simplified further is that one of the parameters would become a value that is not possible given the constraints of the problem.

In our example problem, we have two changing parameters, S and P. Let’s think about what possible values of S and P might not be legal:

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

Sometimes it can be a little challenging to convert assertions that we make about parameters into programmable base cases. This is because, in addition to listing the assertions if you want to make your code look concise and not check for unnecessary conditions, you also need to think about which of these conditions are even possible.

In our example:

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

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

The way we talked about the steps so far might lead you to think that we should implement the problem recursively. However, everything that we’ve talked about so far is completely agnostic to whether you decide to implement the problem recursively or iteratively. In both approaches, you would have to determine the recurrence relation and the base cases.

To decide whether to go iteratively or recursively, you want to carefully think about the trade-offs .

Stack overflow issues are typically a deal breaker and a reason why you would not want to have recursion in a (backend) production system. However, for the purposes of the interview, as long as you mention the trade-offs, you should typically be fine with either of the implementations. You should feel comfortable implementing both.

In our particular problem, I implemented both versions. Here is python code for that: A recursive solution: (original code snippets can be found here )

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

Step 6: Add memoization

Memoization is a technique that is closely associated with DP. It is used for storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Why are we adding memoization to our recursion? We encounter the same subproblems which, without memoization, are computed repeatedly. Those repetitions very often lead to exponential time complexities.

In recursive solutions, adding memoization should feel straightforward. Let’s see why. Remember that memoization is just a cache of the function results. There are times when you want to deviate from this definition in order to squeeze out some minor optimizations, but treating memoization as a function result cache is the most intuitive way to implement it.

This means that you should:

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

Here is the code from above with added memoization (added lines are highlighted): (original code snippets can be found here )

In order to illustrate the effectiveness of memoization and different approaches, let’s do some quick tests. I will stress test all three methods that we have seen so far. Here is the set up:

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

Here are the results (in seconds):

You can see that the pure recursive approach takes about 500x more time than the iterative approach and about 1300x more time than the recursive approach with memoization. Note that this discrepancy would grow rapidly with the length of the runway. I encourage you to try running it yourself.

Step 7: Determine Time complexity

There are some simple rules that can make computing time complexity of a dynamic programming problem much easier. Here are two steps that you need to do:

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

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

• P is the set of all positions (|P| indicates the number of elements in P)
• S is the set of all speeds

The work done per each state is O(1) in this problem because, given all other states, we simply have to look at 3 subproblems to determine the resulting state.

As we noted in the code before, |S| is limited by length of the runway (|P|), so we could say that the number of states is |P|² and because work done per each state is O(1), then the total time complexity is O(|P|²).

However, it seems that |S| can be further limited, because if it were really |P|, it is very clear that stopping would not be possible because you would have to jump the length of the entire runway on the first move.

So let’s see how we can put a tighter bound on |S|. Let’s call maximum speed S. Assume that we’re starting from position 0. How quickly could we stop if we were trying to stop as soon as possible and if we ignore potential spikes?

In the first iteration, we would have to come at least to the point (S-1), by adjusting our speed at zero by -1. From there we would at a minimum go by (S-2) steps forward, and so on.

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

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

=> S*(S-1) / 2 < L

=> S² — S — 2L < 0

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

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

We can write our inequality as:

(S — r1) * (S — r2) < ; 0

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

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

=> S < 1/2 + sqrt(1/4 + 2L)

That is the maximum speed that we could possibly have on a runway of a length L. If we had a speed higher than that, we could not stop even theoretically, irrespective of the position of the spikes.

That means that the total time complexity depends only on the length of the runway L in the following form:

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

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

Awesome, you made it through! :)

The 7 steps that we went through should give you a framework for systematically solving any dynamic programming problem. I highly recommend practicing this approach on a few more problems to perfect your approach.

Here are some next steps that you can take

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

When you feel like you’ve conquered these ideas, check out Refdash where you are interviewed by a senior engineer and get a detailed feedback on your coding, algorithms, and system design.

Originally published at Refdash blog . Refdash is an interviewing platform that helps engineers interview anonymously with experienced engineers from top companies such as Google, Facebook, or Palantir and get a detailed feedback. Refdash also helps engineers discover amazing job opportunities based on their skills and interests.

If this article was helpful, share it .

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

• Trending Now
• Foundational Courses
• Data Science
• Practice Problem
• Machine Learning
• System Design
• DevOps Tutorial

Welcome to our comprehensive tutorial on unraveling Dynamic Programming (DP)! Whether you're a novice programmer or an experienced developer delving into optimization techniques, this tutorial is crafted to demystify Dynamic Programming for you.

In this tutorial, we'll delve into the intricate world of Dynamic Programming, providing clear explanations, intuitive examples, and step-by-step solutions to classic DP problems. From understanding the underlying principles to implementing DP algorithms for various problem types, we'll cover everything you need to know to master this powerful algorithmic paradigm.

Join us as we unravel the mysteries of Dynamic Programming, exploring its applications in solving optimization problems, sequence alignment, graph traversal, and more. We'll discuss dynamic programming formulations, memoization, tabulation, and advanced optimization techniques to tackle problems efficiently.

Ready to elevate your problem-solving skills and become proficient in Dynamic Programming? Watch the tutorial now and unlock the full potential of this transformative algorithmic paradigm! For further exploration and detailed insights, don't forget to peruse the accompanying article on GeeksforGeeks: https://www.geeksforgeeks.org/dynamic-programming/

Don't miss out on the opportunity to expand your algorithmic repertoire and master Dynamic Programming. Like, share, and subscribe for more tutorials and insights into algorithmic problem-solving. Let's embark on this enlightening journey together. Happy coding!

• [email protected]

What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

• Don’t have an account Yet? Sign Up

Remember me Forgot your password?

• Already have an Account? Sign In

Lost your password? Please enter your email address. You will receive a link to create a new password.

Back to log-in

By Signing up for Favtutor, you agree to our Terms of Service & Privacy Policy.

Dynamic Programming in Python: Top 10 Problems (with code)

• May 25, 2023
• 15 Minutes Read
• Why Trust Us We uphold a strict editorial policy that emphasizes factual accuracy, relevance, and impartiality. Our content is crafted by top technical writers with deep knowledge in the fields of computer science and data science, ensuring each piece is meticulously reviewed by a team of seasoned editors to guarantee compliance with the highest standards in educational content creation and publishing.
• By Shivali Bhadaniya

In this article, you will learn what Dynamic Programming is, the approach to solving problems using it, the principle of optimality, and how you can solve dynamic programming along with its characteristics and elements. We will also go through the 10 most important dynamic programming problems in Python. So, let's get started!

What is Dynamic Programming?

Just like the divide and conquer algorithm , Dynamic Programming solves problems by combining the solutions with sub-problems.

Divide and conquer algorithms partition the problem into independent sub-problems to solve the sub-problems recursively and then combine their solutions to solve the original problem. In contrast, dynamic programming is applicable when the sub-problem is not independent, that is when sub-problems share sub-problems.

Therefore, a dynamic programming algorithm solves every sub-problem just once and then saves its answers in a table, thereby avoiding the work of recomputing the answer every time the subproblem is encountered.

The development of a dynamic programming algorithm can be broken into a sequence of four steps:

• Characterize the structure of an optimal solution
• Recursively define the value of the optimal solution
• Compute the value of an optimal solution in a bottom-up fashion
• Construct an optimal solution from computed information

Dynamic programming algorithm is designed in a way to optimize the given problem to get output by combining the solutions of sub-problems and appearing to the “principle of optimality”.

What is the Principle of Optimality?

The dynamic programming algorithm obtains the solution using the principle of optimality. The principle of optimality states that “ in an optimal sequence of decisions or choices, each subsequence must also be optimal”. When it is not possible to apply the principle of optimality it is almost impossible to obtain the solution using the dynamic programming approach.

The principle of optimality : “If k is a node on the shortest path from i to j, then the part of the path from i to k, and the part from k to i, must also be optimal.”

How to Solve Dynamic Programming Problems?

After knowing what dynamic programming is, it is important to learn the recipe for solving dynamic programming problems. When it comes to finding the solution to the problem using dynamic programming, below are the few steps you should consider to follow:

1) Recognize the DP problem

Identifying that the given problem statement can be solved by a dynamic programming algorithm is the most crucial step. You can solve this difficulty by asking yourself whether you can divide the given problem statements into smaller parts as a function and find its solution or not.

2) Identify problem variables

After deciding that the problem can be solved using dynamic programming, the next thing you have to do is to find the recursive structure between the subproblems of the original problem. Here, you have to consider the changing parameters of the problem. This changing parameter can be anything like the array position or the speed of the problem-solving.

Also, it is important to identify the number of subproblems of the original problem.

3) Express the recurrence relation

Many developers rush through the coding part of problem-solving and forget to define the recurrence relation. Expressing the recurrence relation clearly before coding the problem will strengthen your problem understanding and make the process efficient.

4) Identify the base case

The case is a part of the subproblem which is independent of other subproblems. In order to define the base case of your subproblem, you have to identify the point at which your problem cannot be simplified further.

5) Decide the iterative or recursive approach

Dynamic programming problems can be solved using an iterative or recursive approach. By the discussion till now, you must assume that the recursive process is better. But it is important to know that all the above points we discussed are completely independent of the problem-solving approach.

Whether you choose the iterative method or the recursive method, it is important for you to decide the recurrence relation and the base case of the problem.

6) Add memoization

Memoization is the process of storing the result of the subproblem and calling them again when a similar subproblem is to be solved. This will reduce the time complexity of the problem. If we do not use memorization, similar subproblems are repeatedly solved which can lead to exponential time complexities.

Characteristics and Elements

Before applying the dynamic programming approach to a problem statement, it is important to know that when to apply a dynamic programming algorithm. Let us understand 2 characteristics of the dynamic problem which explain the working while solving the problem statement.

1) Optimal substructure

The problem gives the optimal substructure if the optimal solution contains optimal sub-solutions in it. We can recursively define the optimal solution if the problem has an optimal substructure. Also, there is no base to define a recursive algorithm if the problem doesn’t have an optimal solution.

2) Overlapping subproblems

The problem is called overlapping subproblems if the recursive algorithm repeatedly visits the same sub-problems. If any problem has overlapping subproblems then we can improve the repetitive implementation of sub-problems by computing it only once. If the problem doesn’t have overlapping subproblems, then it is not feasible to use a dynamic programming algorithm to solve the problem.

As you have understood, dynamic programming is the algorithm that divides the problem into various sub-problems to find out the optimal solution. While solving the problem statement using the dynamic programming approach, the problem is divided into 3 elements in total to get the final result. These elements are:

• Substructure:  Sub-Structuring is the process of dividing the given problem statement into smaller sub-problems. Here we manage to identify the solution of the original problem in terms of the solution of sub-problems.
• Table Structure: It is necessary to store the solution of the sub-problem into a table after solving it. This is important because as we know, dynamic programming reuse the solutions of subproblems many times so that we don’t have to repeatedly solve the same problem, again and again,
• Bottom-up approach: The process of combining the solutions of subproblems to achieve the final result using the table. The process starts with solving the smallest subproblem and later combining their solution with the subproblems of increasing size until you get the final solution of the original problem.

Top 10 Dynamic Programming Problems in Python

There are many problem statements that are solved using a dynamic programming approach to find the optimal solution. Some of the most commonly asked well-known problem statements are discussed below with a brief explanation and their corresponding Python code.

1) Knapsack (0-1) Bounded

Here, you are given the profits and weights of N items, and you have to put these items in a knapsack with the capacity ‘W’, and you have to find the number of items to be selected such that it is less than or equal to the knapsack capacity.

The knapsack problem is the perfect example of a dynamic programming algorithm and the most commonly asked question in a technical interview of product-based companies.

Problem Statement: Given a bag with capacity W and a list of items along with their weights and profit associated with them. The task is to fill the bad efficiently such that max profit is achieved.

Solution: Here, you will create a table dp[][] and consider all possible weights from 1 to W as columns and weights that you can choose as rows. The state /cell dp[i][j] in the table represents the maximum attainable profit if 'j' is the capacity of the knapsack and the first 'i' elements are included in the weight/ item array.

Thus the last cell will represent the answer state. Items can only be included if their weight is less than the capacity of the knapsack. There are two possibilities for the condition where you can fill all columns which have ‘weight>wt[i-1]’. Check out these two possibilities in detail as shown in the below problem logic:

Problem Logic:

Python Code:

The running time complexity of the 0/1 Knapsack problem is O(N*W) where N is the number of items given and W is the capacity of the Knapsack.

2) 0/1 Knapsack Bounded Memoization

You are given a bag with the capacity K and a list of items with specified weight and profit that are to be inserted such that you get the maximum profit. Here we will try to solve the problem using memoization rather than tabulation.

The difference between both the 0/1 knapsack problem is that the above problem used the bottom-up approach to find the solution whereas this problem uses a top-down approach using memoization to get the output of the problem.

The reason to use memoization is that it helps to reduce the overlapping of subproblems in dynamic programming. Therefore, it reduces the problem of repeatedly solving the sub-problem and makes the process getting output faster and more effective.

Problem Statement: Given a bag with capacity W and a list of items along with their weights and profit associated with them. The task is to fill the bag efficiently such that max profit is achieved.

Solution: Firstly, you have to create a 2D array to store the results of all the subproblems which are solved. The columns of the table will display all possible weights from 1..W dividing it into W parts and rows displaying the weights you choose at any given moment. 

Every time we solve a subproblem we store it in a dp array. Whenever we encounter the same subproblem we simply return the solution rather than solving it again.

The running time complexity of the problem is O(N*W) where N is the number of items present and W is the capacity of the knapsack.

3) Subset Sum Problem

The subset sum problem is the most frequently asked question in technical interviews with Microsoft and Infosys. The subset sum problem is the problem of finding the subset of the given set of numbers where the sum of the elements of the subset found is equal to the target number.

Problem statement: You are given an array and target. You have to find if there exists any subset that will sum equal to the target.

Solution: Here you will create a 2D array of size (arra.size()+1)*(target+1) of boolean type. Later, you will set the value of each state dp[i][j] true if a subset of elements arr[0...i] exists with the sum value to be 'j' where j is the target number. 

Python code:

The time complexity of the above problem is O(target sum*n), where n is the size of the array. 

4) Equal Subset Problem

The equal subset problem uses dynamic programming to find the partition of the given set such that the sum of elements of both subsets is the same. The equal subset problem is also known as the partition problem and is a very good example of a dynamic programming algorithm.

Problem Statement: Given an array arr. You have to divide the array into halves such that the sum of the two subsets is equal.

Solution: You have to create a 2D array of size (sum/2+1)*(target+1). Here, you can store the output for every subset and every sum and then retrieve the output while partitioning the original array. The first dimension in the 2D array will represent the different possibilities of subset and the second dimension will represent the different possibilities of sum using the combinations of subsets.

The running time complexity of the above code is O(target*n) where the target is the ‘target sum’ and n is the length of the array

5) Longest Common Subsequence

The longest common subsequence problem is the most commonly asked question in Google Interview. Here the problem involves finding the longest subsequence that is present in the two given strings in the same order. Therefore, the output should be the longest sequence that can be obtained by deleting some items from the first and second original strings. 

Problem Statement:  You are given two strings s1 and s2, of length l1 and l2, respectively. You have to find the length of the longest common subsequence of s1 and s2.

Solution:  This problem differs from the Longest Common Substring problem as in substrings, sequences are not necessary to occupy consecutive positions within the original string. Solving this problem using a dynamic programming approach will reduce the number of function calls to find the common sequence. 

Using dynamic programming, you have to generate a table dp(1..m, 1…n) where m is the length of string s1 and n is the length of string s2.

At any instance, if the characters of two strings match then you increment the value from the previous subproblem else you look for an answer by taking the maximum from two subproblems created by decrement either string by one i.e., looking for characters other than unmatched characters.

Problem Logic to generate the table dp[i][j] as shown below where i and j represent the row and column of the table. 

The time complexity of the above problem is O(m*n), where m is the length of s1 and n is the length of s2.

6) Longest Common Substring

The longest common substring problem is the problem of finding the longest string which is also the substring of two different strings. Sounds confusing? Let's look forward and understand it in detail.  

Problem Statement: You are given the strings s1 and s2. You have to find the length of the longest common substring of s1 and s2.

Solution:  Here you can start checking all substrings from the first string s1 with the character of the second string s2 and keep a record of the maximum. You can solve this problem using dynamic programming by following the bottom-up manner.

Create a matrix of size len(s1)*len(s2) and store the value of the solutions of the substrings to use later to solve similar subproblems. The problem is similar to the Longest Common Subsequence problem with the only difference that if the characters do not match then the answer at that instance becomes 0.

The running time complexity of the above problem is O(m*n), where m is the length of s1 and n is the length of s2. 

7) Longest Palindromic Sequence

The largest palindromic sequence problem finds the characters of the sequence from the given string, which are palindromic in nature. It is the sequence of characters that are read and spelled in the same way from forward and backward. Unlike the longest palindromic substring problem, the sequences may or may not occupy consecutive positions within the original string.  

Problem Statement: Given a string ‘S’. The task is to find the length of the largest palindromic sequence.

Solution: Here, the problem shows the characteristics of the dynamic programming approach i.e., optimal substructure and overlapping subproblems. The problem shows a direct resemblance with the Longest Common Substring problem. But How?? You are given only one string!

Even though you are given only a string, by close observation we find that the Longest Palindromic Subsequence is actually the Longest Common Substring between the string and its reverse.

The time complexity of the above problem is O(2^n), where n is the length of the given string.

8) Longest Repeating Subsequence

The longest Repeating subsequence serves as the best example of a dynamic programming problem. The problem gets the output of the longest sequence of characters from the given string which is repeated irrespective of the order of the string

Problem Statement: Given a string s. Find the length of the largest repeating subsequence in it.

Solution: The longest repeating subsequence problem is the modified version of the longest common subsequence problem. Therefore, in this problem, you have to find the longest common subsequence of the string where the given string will itself be s1 and s2 for the LCS problem. T

herefore, you have to ignore the case where the indexes of both string are the same while comparing the characters as the repeated character hold a different index in the given string

This problem contains the characteristic of dynamic programming i.e. overlapping and optimal structure, you can divide the problem into several subproblems just like the LCS problem, and store the result of each problem in the table.

The running time complexity to find the longest repeating subsequence is O(n^2) where n is the length of the input string.

9) Coin Change Minimum Problem

This is one of the famous dynamic programming problems which is mostly asked in technical interviews for getting into top companies. Here, the minimum coin change problem is to make a change of the given value of cents where you have an infinite supply of each of C = {c1, c2,….cm} valued coins.

Problem Statement: Given an array of available denominations of coin and one target price. Find the minimum number of coins required to pay the same.

Solution: Here, you can start the solution with sum = N cents. In each iteration, find the minimum coins required by dividing the original problem into subproblems.

Consider a coin from { 1, c2,…cm} and reduce the sum repeatedly depending upon the coin of the denomination you choose. You have to repeat the same process until N becomes 0, and at this point, you found your solution.

The running time complexity of the coin change minimum problem is O(m*n), where m is the number of coins and n is the change required. 

10) Coin Change Ways

Coin change ways is a similar problem to the coin change problem that you learned earlier. Here, you are given value N and you have to make a change of these N cents with an infinite supply of each c=(c1, c2, ..cn) valued coin. Unlike the coin change problem, in this problem, you have to find out the distinct number of ways to make change for N cents.

Remember here the order of the coin doesn’t matter.

Problem Statement: Given an array of available denominations of coin and one target price. In how many ways can you pay the price provided you can use any coin any number of times?

Solution: Here you can see that the problem has characteristics of a dynamic programming approach i.e. optimal structure and overlapping subproblem nature and therefore, you can solve the above problem easily using dynamic programming. To solve the problem, you have to create a 2D array to store the subproblem solution.

The size of the table ‘dp’ will be (n+1)*(price+1). The rows of the table will display the denomination of coins and the column will display the total amount i.e. the sum of the cents. We will repeatedly store the value of each subproblem in the DP table and the value in the last row and the last column of the table is the final answer.

Compare the denomination value and the sum value repeatedly and run the loop to find the result of each subproblem and solve it in the table. Check out the below problem logic for a better understanding of the solution to the problem.

The time complexity of the above problem is O(n*N) where n is the total number of denominations and N is the total change required.

House Robber is another big problem that was asked about in coding interviews.

Dynamic Programming vs Greedy Programming

Here is a complete table of differences between Dynamic and Greedy programming:

Learn more about greedy programming .

Advantages & Disadvantages

The biggest advantages of Dynamic Programming is that you can obtain the both local and total optimal solution, it reduces the lines of the code, & it is applicable to both linear and non-linear problem.

However, DP makes unnecessary memory utilization. As you make use of the table while solving the problem, it needs a lot of memory space for storage purposes

Applications of Dynamic Programming

Following are some major practical applications of Dynamic Programming:

• It is used in the 0/1 Knapsack Problem which is most commonly asked in technical interviews.
• It is used in a time-sharing scheduling algorithm.
• It is used widely while solving a mathematical optimization problem.
• It is used in flight and robotics control.
• It is used in routing algorithms.
• It is mostly used in computer networks and graph problems.

What are Sub Programs in Dynamic Programming?

By dividing a problem through smaller subproblems as well as storing the solutions for these smaller subproblems, dynamic programming provides a strategy for problem-solving. In dynamic programming, we resolve an issue by first resolving its sub-issues, then combining their resolutions to resolve the issue at hand.

A subproblem is a scaled-down version of the main problem. We divide the main problem into smaller, similarly structured, but more manageable subproblems. Although each subproblem is easier to tackle, they all share the same structure as the main issue. Recursively addressing the subproblems, we find solutions and record them in a table.

The fundamental problem is then resolved using the subproblem solutions. Take the issue of locating the nth Fibonacci number as an illustration. This issue can be resolved via dynamic programming by dissecting it into smaller issues.

The sum of the (n-1)th and (n-2)th Fibonacci numbers is the nth Fibonacci number. As a result, we may get the (n-1)st and (n-2)st Fibonacci numbers and then add them to solve the issue recursively. To avoid having to compute the answers to the subproblems again, we can store them in a table and utilize them to calculate the answer to the main problem.

What is Memorisation in Dynamic Programming?

Dynamic programming uses the memory approach to save the outcomes of subproblems in a table so they can be reused later. Memory is a type of caching that is employed to quicken the process of problem-solving.

When a subproblem is encountered again, the outcome of the previous subproblem is stored in a table and can be retrieved using memory. As there is no need to solve the same subproblem more than once, this method can greatly reduce the algorithm's time complexity.

Take the Fibonacci sequence, for instance. The formula F(n) = F(n-1) + F(n-2) defines the series, where F(0) = 0 and F(1) = 1. With the aid of dynamic programming and memoization, we can identify the nth phrase in the sequence. The solution to each subproblem can be kept in a table and used to determine the sequence's subsequent term.

By using this method, the algorithm's time complexity is reduced from exponential to linear. A table or an array can be used to implement memory by storing the outcomes of subproblems. As the algorithm resolves each subproblem, the values in the table can be changed. The table can be initialized with default values.

It is possible to use memorization for issues with overlapping subproblems, which means that the algorithm will run into the same subproblem more than once.

When should it be used to solve a problem?

The powerful method of dynamic programming can be applied to a variety of issues. However, there are several requirements that must be satisfied before choosing to utilize dynamic programming to solve an issue, therefore it isn't always the best option.

• Overlapping Subproblems: The existence of overlapping subproblems in the original problem is one of the essential conditions for dynamic programming. In other words, the issue can be divided into more manageable subproblems that are used repeatedly in the resolution.
• Optimal substructure: The problem's optimal substructure is another prerequisite for dynamic programming. In other words, the problem's optimal solution can be created from the answers to its individual subproblems.
• Memory work can enhance performance: By saving the outcomes of pricey function calls in memory, dynamic programming methods can run better. Memorization can drastically lower the number of function calls necessary if the same subproblem appears numerous times in the solution.
• Complexity in polynomial time: Algorithms for dynamic programming should have polynomial time complexity. That is, the amount of time needed to solve the issue should be inversely correlated with some polynomial function of the size of the input.

Dynamic programming in Python is most important to optimize the solutions to the problem in comparison to the recursive approach. It helps to reduce the repeated function calls and hence proves to be faster and more effective than the recursive and divide-and-conquer approaches.

The idea of simply storing the results of subproblems and making use of them in computing the rest of the problem make dynamic programming algorithm a different and important topic in the domain of data structure and algorithm. Therefore, it is surely asked in every technical interview and highly recommended to learn and understand.

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author

Shivali Bhadaniya

More by favtutor blogs, monte carlo simulations in r (with examples), aarthi juryala.

The unlist() Function in R (with Examples)

Paired Sample T-Test using R (with Examples)

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

Theoretical Approaches to Non-Numerical Problem Solving pp 274–280 Cite as

Dynamic Programming and Problem-Solving

• Richard Bellman 4  
• Conference paper

149 Accesses

Part of the book series: Lecture Notes in Operations Research and Mathematical Systems ((LNE,volume 28))

A device that can perform the elementary operations of arithmetic rapidly and accurately and store the results of these calculations in order to use them at appropriate times according to assigned instructions necessarily must exert a strong influence upon any field in which significant problems can be quantized. It is obvious therefore that the digital computer plays a role of increasing importance in science and engineering. What is not as clear is the magnitude or kind of influence. The second computer revolution, the overthrow of the concepts and methodology of the seventeenth and eighteenth centuries, will be far more dramatic than the first which consisted merely in an accelerated use of the methods and methodology of these bygone eras.

Supported by the National Institutes of Health under Grant No. GM 16197-01 and GM 16197-02.

This is a preview of subscription content, log in via an institution .

Buying options

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Unable to display preview.  Download preview PDF.

Bellman, R., Cooke, K.L. and Lockett, J., Algorithms, Graphs, and Computers . Academic Press Inc., New York, to appear

Google Scholar  

Bellman, R., Adaptive Control Processes: A Guided Tour , Princeton University Press, Princeton, New Jersey, 1961

MATH   Google Scholar  

Bellman, R., “On a Routing Problem,” C. Appl. Math ., Vol. 16, pp. 87–90, 1968

Bellman, R., “Dynamic Programming Treatment of the Traveling Salesman Problem,” J. Assoc. Comput. Machinery , Vol. 9, pp. 61–63, 1962

Article   MATH   Google Scholar  

Bellman, R., “Dynamic Programming and Difficult Crossing Puzzles,” Math. Mag ., January-February, pp. 27–29, 1962

Bellman, R., and Cooke, K.L., “The Konigsberg Bridges Problem Generalized,” J. Math. Anal. Appl ., Vol. 25, 1969

Bellman, R., “On Some Mathematical Recreations,” Amer. Math. Monthly , Vol. 69, pp. 640–643, 1962

Article   MathSciNet   MATH   Google Scholar  

Bellman, R., “Dynamic Programming and Lewis Carroll’s Game of Doublets,” B. Inst. Math, and its Appl ., to appear

Bellman, R., and Gluss, B., “On Various Versions of the Defective Coin Problem,” Information and Control , Vol. 4, pp. 118–131, 1961

Article   Google Scholar  

Bellman, R., “An Application of Dynamic Programming to the Coloring of Maps, ICC Bull ., Vol. 4, pp. 3–6, 1965

MathSciNet   Google Scholar  

Bellman, R., “Stratification and the Control of Large Systems with Applications to Chess and Checkers,” Information Sciences , Vol. 1, pp. 7–21, 1968

Bellman, R., “On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers,” Proc. Nat. Acad. Sci. USA , Vol. 53, pp. 244–247, 1965

Howard, R., Dynamic Programming and Markovian Decision Processes , M.I.T. Press, Cambridge, Massachusetts, 1965

Download references

Author information

Authors and affiliations.

Department of Mathematics, Electrical Engineering, and Medicine University of Southern California, Los Angeles, California, USA

Richard Bellman

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

Systems Research Center, Case Western Reserve University, Cleveland, Ohio, USA

R. B. Banerji  & M. D. Mesarovic  & 

Rights and permissions

Reprints and permissions

Copyright information

© 1970 Springer-Verlag Berlin · Heidelberg

About this paper

Cite this paper.

Bellman, R. (1970). Dynamic Programming and Problem-Solving. In: Banerji, R.B., Mesarovic, M.D. (eds) Theoretical Approaches to Non-Numerical Problem Solving. Lecture Notes in Operations Research and Mathematical Systems, vol 28. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-99976-5_10

Download citation

DOI : https://doi.org/10.1007/978-3-642-99976-5_10

Publisher Name : Springer, Berlin, Heidelberg

Print ISBN : 978-3-540-04900-5

Online ISBN : 978-3-642-99976-5

eBook Packages : Springer Book Archive

Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

• View all journals
• My Account Login
• Explore content
• About the journal
• Publish with us
• Sign up for alerts
• Open access
• Published: 10 April 2024

A hybrid particle swarm optimization algorithm for solving engineering problem

• Jinwei Qiao 1 , 2 ,
• Guangyuan Wang 1 , 2 ,
• Zhi Yang 1 , 2 ,
• Xiaochuan Luo 3 ,
• Jun Chen 1 , 2 ,
• Kan Li 4 &
• Pengbo Liu 1 , 2  

Scientific Reports volume  14 , Article number:  8357 ( 2024 ) Cite this article

149 Accesses

Metrics details

• Computational science
• Mechanical engineering

To overcome the disadvantages of premature convergence and easy trapping into local optimum solutions, this paper proposes an improved particle swarm optimization algorithm (named NDWPSO algorithm) based on multiple hybrid strategies. Firstly, the elite opposition-based learning method is utilized to initialize the particle position matrix. Secondly, the dynamic inertial weight parameters are given to improve the global search speed in the early iterative phase. Thirdly, a new local optimal jump-out strategy is proposed to overcome the "premature" problem. Finally, the algorithm applies the spiral shrinkage search strategy from the whale optimization algorithm (WOA) and the Differential Evolution (DE) mutation strategy in the later iteration to accelerate the convergence speed. The NDWPSO is further compared with other 8 well-known nature-inspired algorithms (3 PSO variants and 5 other intelligent algorithms) on 23 benchmark test functions and three practical engineering problems. Simulation results prove that the NDWPSO algorithm obtains better results for all 49 sets of data than the other 3 PSO variants. Compared with 5 other intelligent algorithms, the NDWPSO obtains 69.2%, 84.6%, and 84.6% of the best results for the benchmark function ( \({f}_{1}-{f}_{13}\) ) with 3 kinds of dimensional spaces (Dim = 30,50,100) and 80% of the best optimal solutions for 10 fixed-multimodal benchmark functions. Also, the best design solutions are obtained by NDWPSO for all 3 classical practical engineering problems.

Similar content being viewed by others

A clustering-based competitive particle swarm optimization with grid ranking for multi-objective optimization problems

Qianlin Ye, Zheng Wang, … Mengjiao Yu

A modified shuffled frog leaping algorithm with inertia weight

Zhuanzhe Zhao, Mengxian Wang, … Zhibo Liu

Appropriate noise addition to metaheuristic algorithms can enhance their performance

Kwok Pui Choi, Enzio Hai Hong Kam, … Weng Kee Wong

Introduction

In the ever-changing society, new optimization problems arise every moment, and they are distributed in various fields, such as automation control 1 , statistical physics 2 , security prevention and temperature prediction 3 , artificial intelligence 4 , and telecommunication technology 5 . Faced with a constant stream of practical engineering optimization problems, traditional solution methods gradually lose their efficiency and convenience, making it more and more expensive to solve the problems. Therefore, researchers have developed many metaheuristic algorithms and successfully applied them to the solution of optimization problems. Among them, Particle swarm optimization (PSO) algorithm 6 is one of the most widely used swarm intelligence algorithms.

However, the basic PSO has a simple operating principle and solves problems with high efficiency and good computational performance, but it suffers from the disadvantages of easily trapping in local optima and premature convergence. To improve the overall performance of the particle swarm algorithm, an improved particle swarm optimization algorithm is proposed by the multiple hybrid strategy in this paper. The improved PSO incorporates the search ideas of other intelligent algorithms (DE, WOA), so the improved algorithm proposed in this paper is named NDWPSO. The main improvement schemes are divided into the following 4 points: Firstly, a strategy of elite opposition-based learning is introduced into the particle population position initialization. A high-quality initialization matrix of population position can improve the convergence speed of the algorithm. Secondly, a dynamic weight methodology is adopted for the acceleration coefficients by combining the iterative map and linearly transformed method. This method utilizes the chaotic nature of the mapping function, the fast convergence capability of the dynamic weighting scheme, and the time-varying property of the acceleration coefficients. Thus, the global search and local search of the algorithm are balanced and the global search speed of the population is improved. Thirdly, a determination mechanism is set up to detect whether the algorithm falls into a local optimum. When the algorithm is “premature”, the population resets 40% of the position information to overcome the local optimum. Finally, the spiral shrinking mechanism combined with the DE/best/2 position mutation is used in the later iteration, which further improves the solution accuracy.

The structure of the paper is given as follows: Sect. “ Particle swarm optimization (PSO) ” describes the principle of the particle swarm algorithm. Section “ Improved particle swarm optimization algorithm ” shows the detailed improvement strategy and a comparison experiment of inertia weight is set up for the proposed NDWPSO. Section “ Experiment and discussion ” includes the experimental and result discussion sections on the performance of the improved algorithm. Section “ Conclusions and future works ” summarizes the main findings of this study.

Literature review

This section reviews some metaheuristic algorithms and other improved PSO algorithms. A simple discussion about recently proposed research studies is given.

Metaheuristic algorithms

A series of metaheuristic algorithms have been proposed in recent years by using various innovative approaches. For instance, Lin et al. 7 proposed a novel artificial bee colony algorithm (ABCLGII) in 2018 and compared ABCLGII with other outstanding ABC variants on 52 frequently used test functions. Abed-alguni et al. 8 proposed an exploratory cuckoo search (ECS) algorithm in 2021 and carried out several experiments to investigate the performance of ECS by 14 benchmark functions. Brajević 9 presented a novel shuffle-based artificial bee colony (SB-ABC) algorithm for solving integer programming and minimax problems in 2021. The experiments are tested on 7 integer programming problems and 10 minimax problems. In 2022, Khan et al. 10 proposed a non-deterministic meta-heuristic algorithm called Non-linear Activated Beetle Antennae Search (NABAS) for a non-convex tax-aware portfolio selection problem. Brajević et al. 11 proposed a hybridization of the sine cosine algorithm (HSCA) in 2022 to solve 15 complex structural and mechanical engineering design optimization problems. Abed-Alguni et al. 12 proposed an improved Salp Swarm Algorithm (ISSA) in 2022 for single-objective continuous optimization problems. A set of 14 standard benchmark functions was used to evaluate the performance of ISSA. In 2023, Nadimi et al. 13 proposed a binary starling murmuration optimization (BSMO) to select the effective features from different important diseases. In the same year, Nadimi et al. 14 systematically reviewed the last 5 years' developments of WOA and made a critical analysis of those WOA variants. In 2024, Fatahi et al. 15 proposed an Improved Binary Quantum-based Avian Navigation Optimizer Algorithm (IBQANA) for the Feature Subset Selection problem in the medical area. Experimental evaluation on 12 medical datasets demonstrates that IBQANA outperforms 7 established algorithms. Abed-alguni et al. 16 proposed an Improved Binary DJaya Algorithm (IBJA) to solve the Feature Selection problem in 2024. The IBJA’s performance was compared against 4 ML classifiers and 10 efficient optimization algorithms.

Improved PSO algorithms

Many researchers have constantly proposed some improved PSO algorithms to solve engineering problems in different fields. For instance, Yeh 17 proposed an improved particle swarm algorithm, which combines a new self-boundary search and a bivariate update mechanism, to solve the reliability redundancy allocation problem (RRAP) problem. Solomon et al. 18 designed a collaborative multi-group particle swarm algorithm with high parallelism that was used to test the adaptability of Graphics Processing Units (GPUs) in distributed computing environments. Mukhopadhyay and Banerjee 19 proposed a chaotic multi-group particle swarm optimization (CMS-PSO) to estimate the unknown parameters of an autonomous chaotic laser system. Duan et al. 20 designed an improved particle swarm algorithm with nonlinear adjustment of inertia weights to improve the coupling accuracy between laser diodes and single-mode fibers. Sun et al. 21 proposed a particle swarm optimization algorithm combined with non-Gaussian stochastic distribution for the optimal design of wind turbine blades. Based on a multiple swarm scheme, Liu et al. 22 proposed an improved particle swarm optimization algorithm to predict the temperatures of steel billets for the reheating furnace. In 2022, Gad 23 analyzed the existing 2140 papers on Swarm Intelligence between 2017 and 2019 and pointed out that the PSO algorithm still needs further research. In general, the improved methods can be classified into four categories:

Adjusting the distribution of algorithm parameters. Feng et al. 24 used a nonlinear adaptive method on inertia weights to balance local and global search and introduced asynchronously varying acceleration coefficients.

Changing the updating formula of the particle swarm position. Both papers 25 and 26 used chaotic mapping functions to update the inertia weight parameters and combined them with a dynamic weighting strategy to update the particle swarm positions. This improved approach enables the particle swarm algorithm to be equipped with fast convergence of performance.

The initialization of the swarm. Alsaidy and Abbood proposed 27 a hybrid task scheduling algorithm that replaced the random initialization of the meta-heuristic algorithm with the heuristic algorithms MCT-PSO and LJFP-PSO.

Combining with other intelligent algorithms: Liu et al. 28 introduced the differential evolution (DE) algorithm into PSO to increase the particle swarm as diversity and reduce the probability of the population falling into local optimum.

Particle swarm optimization (PSO)

The particle swarm optimization algorithm is a population intelligence algorithm for solving continuous and discrete optimization problems. It originated from the social behavior of individuals in bird and fish flocks 6 . The core of the PSO algorithm is that an individual particle identifies potential solutions by flight in a defined constraint space adjusts its exploration direction to approach the global optimal solution based on the shared information among the group, and finally solves the optimization problem. Each particle \(i\) includes two attributes: velocity vector \({V}_{i}=\left[{v}_{i1},{v}_{i2},{v}_{i3},{...,v}_{ij},{...,v}_{iD},\right]\) and position vector \({X}_{i}=[{x}_{i1},{x}_{i2},{x}_{i3},...,{x}_{ij},...,{x}_{iD}]\) . The velocity vector is used to modify the motion path of the swarm; the position vector represents a potential solution for the optimization problem. Here, \(j=\mathrm{1,2},\dots ,D\) , \(D\) represents the dimension of the constraint space. The equations for updating the velocity and position of the particle swarm are shown in Eqs. ( 1 ) and ( 2 ).

Here \({Pbest}_{i}^{k}\) represents the previous optimal position of the particle \(i\) , and \({Gbest}\) is the optimal position discovered by the whole population. \(i=\mathrm{1,2},\dots ,n\) , \(n\) denotes the size of the particle swarm. \({c}_{1}\) and \({c}_{2}\) are the acceleration constants, which are used to adjust the search step of the particle 29 . \({r}_{1}\) and \({r}_{2}\) are two random uniform values distributed in the range \([\mathrm{0,1}]\) , which are used to improve the randomness of the particle search. \(\omega\) inertia weight parameter, which is used to adjust the scale of the search range of the particle swarm 30 . The basic PSO sets the inertia weight parameter as a time-varying parameter to balance global exploration and local seeking. The updated equation of the inertia weight parameter is given as follows:

where \({\omega }_{max}\) and \({\omega }_{min}\) represent the upper and lower limits of the range of inertia weight parameter. \(k\) and \(Mk\) are the current iteration and maximum iteration.

Improved particle swarm optimization algorithm

According to the no free lunch theory 31 , it is known that no algorithm can solve every practical problem with high quality and efficiency for increasingly complex and diverse optimization problems. In this section, several improvement strategies are proposed to improve the search efficiency and overcome this shortcoming of the basic PSO algorithm.

Improvement strategies

The optimization strategies of the improved PSO algorithm are shown as follows:

The inertia weight parameter is updated by an improved chaotic variables method instead of a linear decreasing strategy. Chaotic mapping performs the whole search at a higher speed and is more resistant to falling into local optimal than the probability-dependent random search 32 . However, the population may result in that particles can easily fly out of the global optimum boundary. To ensure that the population can converge to the global optimum, an improved Iterative mapping is adopted and shown as follows:

Here \({\omega }_{k}\) is the inertia weight parameter in the iteration \(k\) , \(b\) is the control parameter in the range \([\mathrm{0,1}]\) .

The acceleration coefficients are updated by the linear transformation. \({c}_{1}\) and \({c}_{2}\) represent the influential coefficients of the particles by their own and population information, respectively. To improve the search performance of the population, \({c}_{1}\) and \({c}_{2}\) are changed from fixed values to time-varying parameter parameters, that are updated by linear transformation with the number of iterations:

where \({c}_{max}\) and \({c}_{min}\) are the maximum and minimum values of acceleration coefficients, respectively.

The initialization scheme is determined by elite opposition-based learning . The high-quality initial population will accelerate the solution speed of the algorithm and improve the accuracy of the optimal solution. Thus, the elite backward learning strategy 33 is introduced to generate the position matrix of the initial population. Suppose the elite individual of the population is \({X}=[{x}_{1},{x}_{2},{x}_{3},...,{x}_{j},...,{x}_{D}]\) , and the elite opposition-based solution of \(X\) is \({X}_{o}=[{x}_{{\text{o}}1},{x}_{{\text{o}}2},{x}_{{\text{o}}3},...,{x}_{oj},...,{x}_{oD}]\) . The formula for the elite opposition-based solution is as follows:

where \({k}_{r}\) is the random value in the range \((\mathrm{0,1})\) . \({ux}_{oij}\) and \({lx}_{oij}\) are dynamic boundaries of the elite opposition-based solution in \(j\) dimensional variables. The advantage of dynamic boundary is to reduce the exploration space of particles, which is beneficial to the convergence of the algorithm. When the elite opposition-based solution is out of bounds, the out-of-bounds processing is performed. The equation is given as follows:

After calculating the fitness function values of the elite solution and the elite opposition-based solution, respectively, \(n\) high quality solutions were selected to form a new initial population position matrix.

The position updating Eq. ( 2 ) is modified based on the strategy of dynamic weight. To improve the speed of the global search of the population, the strategy of dynamic weight from the artificial bee colony algorithm 34 is introduced to enhance the computational performance. The new position updating equation is shown as follows:

Here \(\rho\) is the random value in the range \((\mathrm{0,1})\) . \(\psi\) represents the acceleration coefficient and \({\omega }{\prime}\) is the dynamic weight coefficient. The updated equations of the above parameters are as follows:

where \(f(i)\) denotes the fitness function value of individual particle \(i\) and u is the average of the population fitness function values in the current iteration. The Eqs. ( 11 , 12 ) are introduced into the position updating equation. And they can attract the particle towards positions of the best-so-far solution in the search space.

New local optimal jump-out strategy is added for escaping from the local optimal. When the value of the fitness function for the population optimal particles does not change in M iterations, the algorithm determines that the population falls into a local optimal. The scheme in which the population jumps out of the local optimum is to reset the position information of the 40% of individuals within the population, in other words, to randomly generate the position vector in the search space. M is set to 5% of the maximum number of iterations.

New spiral update search strategy is added after the local optimal jump-out strategy. Since the whale optimization algorithm (WOA) was good at exploring the local search space 35 , the spiral update search strategy in the WOA 36 is introduced to update the position of the particles after the swarm jumps out of local optimal. The equation for the spiral update is as follows:

Here \(D=\left|{x}_{i}\left(k\right)-Gbest\right|\) denotes the distance between the particle itself and the global optimal solution so far. \(B\) is the constant that defines the shape of the logarithmic spiral. \(l\) is the random value in \([-\mathrm{1,1}]\) . \(l\) represents the distance between the newly generated particle and the global optimal position, \(l=-1\) means the closest distance, while \(l=1\) means the farthest distance, and the meaning of this parameter can be directly observed by Fig.  1 .

Spiral updating position.

The DE/best/2 mutation strategy is introduced to form the mutant particle. 4 individuals in the population are randomly selected that differ from the current particle, then the vector difference between them is rescaled, and the difference vector is combined with the global optimal position to form the mutant particle. The equation for mutation of particle position is shown as follows:

where \({x}^{*}\) is the mutated particle, \(F\) is the scale factor of mutation, \({r}_{1}\) , \({r}_{2}\) , \({r}_{3}\) , \({r}_{4}\) are random integer values in \((0,n]\) and not equal to \(i\) , respectively. Specific particles are selected for mutation with the screening conditions as follows:

where \(Cr\) represents the probability of mutation, \(rand\left(\mathrm{0,1}\right)\) is a random number in \(\left(\mathrm{0,1}\right)\) , and \({i}_{rand}\) is a random integer value in \((0,n]\) .

The improved PSO incorporates the search ideas of other intelligent algorithms (DE, WOA), so the improved algorithm proposed in this paper is named NDWPSO. The pseudo-code for the NDWPSO algorithm is given as follows:

The main procedure of NDWPSO.

Comparing the distribution of inertia weight parameters

There are several improved PSO algorithms (such as CDWPSO 25 , and SDWPSO 26 ) that adopt the dynamic weighted particle position update strategy as their improvement strategy. The updated equations of the CDWPSO and the SDWPSO algorithm for the inertia weight parameters are given as follows:

where \({\text{A}}\) is a value in \((\mathrm{0,1}]\) . \({r}_{max}\) and \({r}_{min}\) are the upper and lower limits of the fluctuation range of the inertia weight parameters, \(k\) is the current number of algorithm iterations, and \(Mk\) denotes the maximum number of iterations.

Considering that the update method of inertia weight parameters by our proposed NDWPSO is comparable to the CDWPSO, and SDWPSO, a comparison experiment for the distribution of inertia weight parameters is set up in this section. The maximum number of iterations in the experiment is \(Mk=500\) . The distributions of CDWPSO, SDWPSO, and NDWPSO inertia weights are shown sequentially in Fig.  2 .

The inertial weight distribution of CDWPSO, SDWPSO, and NDWPSO.

In Fig.  2 , the inertia weight value of CDWPSO is a random value in (0,1]. It may make individual particles fly out of the range in the late iteration of the algorithm. Similarly, the inertia weight value of SDWPSO is a value that tends to zero infinitely, so that the swarm no longer can fly in the search space, making the algorithm extremely easy to fall into the local optimal value. On the other hand, the distribution of the inertia weights of the NDWPSO forms a gentle slope by two curves. Thus, the swarm can faster lock the global optimum range in the early iterations and locate the global optimal more precisely in the late iterations. The reason is that the inertia weight values between two adjacent iterations are inversely proportional to each other. Besides, the time-varying part of the inertial weight within NDWPSO is designed to reduce the chaos characteristic of the parameters. The inertia weight value of NDWPSO avoids the disadvantages of the above two schemes, so its design is more reasonable.

Experiment and discussion

In this section, three experiments are set up to evaluate the performance of NDWPSO: (1) the experiment of 23 classical functions 37 between NDWPSO and three particle swarm algorithms (PSO 6 , CDWPSO 25 , SDWPSO 26 ); (2) the experiment of benchmark test functions between NDWPSO and other intelligent algorithms (Whale Optimization Algorithm (WOA) 36 , Harris Hawk Algorithm (HHO) 38 , Gray Wolf Optimization Algorithm (GWO) 39 , Archimedes Algorithm (AOA) 40 , Equilibrium Optimizer (EO) 41 and Differential Evolution (DE) 42 ); (3) the experiment for solving three real engineering problems (welded beam design 43 , pressure vessel design 44 , and three-bar truss design 38 ). All experiments are run on a computer with Intel i5-11400F GPU, 2.60 GHz, 16 GB RAM, and the code is written with MATLAB R2017b.

The benchmark test functions are 23 classical functions, which consist of indefinite unimodal (F1–F7), indefinite dimensional multimodal functions (F8–F13), and fixed-dimensional multimodal functions (F14–F23). The unimodal benchmark function is used to evaluate the global search performance of different algorithms, while the multimodal benchmark function reflects the ability of the algorithm to escape from the local optimal. The mathematical equations of the benchmark functions are shown and found as Supplementary Tables S1 – S3 online.

Experiments on benchmark functions between NDWPSO, and other PSO variants

The purpose of the experiment is to show the performance advantages of the NDWPSO algorithm. Here, the dimensions and corresponding population sizes of 13 benchmark functions (7 unimodal and 6 multimodal) are set to (30, 40), (50, 70), and (100, 130). The population size of 10 fixed multimodal functions is set to 40. Each algorithm is repeated 30 times independently, and the maximum number of iterations is 200. The performance of the algorithm is measured by the mean and the standard deviation (SD) of the results for different benchmark functions. The parameters of the NDWPSO are set as: \({[{\omega }_{min},\omega }_{max}]=[\mathrm{0.4,0.9}]\) , \(\left[{c}_{max},{c}_{min}\right]=\left[\mathrm{2.5,1.5}\right],{V}_{max}=0.1,b={e}^{-50}, M=0.05\times Mk, B=1,F=0.7, Cr=0.9.\) And, \(A={\omega }_{max}\) for CDWPSO; \({[r}_{max},{r}_{min}]=[\mathrm{4,0}]\) for SDWPSO.

Besides, the experimental data are retained to two decimal places, but some experimental data will increase the number of retained data to pursue more accuracy in comparison. The best results in each group of experiments will be displayed in bold font. The experimental data is set to 0 if the value is below 10 –323 . The experimental parameter settings in this paper are different from the references (PSO 6 , CDWPSO 25 , SDWPSO 26 , so the final experimental data differ from the ones within the reference.

As shown in Tables 1 and 2 , the NDWPSO algorithm obtains better results for all 49 sets of data than other PSO variants, which include not only 13 indefinite-dimensional benchmark functions and 10 fixed-multimodal benchmark functions. Remarkably, the SDWPSO algorithm obtains the same accuracy of calculation as NDWPSO for both unimodal functions f 1 –f 4 and multimodal functions f 9 –f 11 . The solution accuracy of NDWPSO is higher than that of other PSO variants for fixed-multimodal benchmark functions f 14 -f 23 . The conclusion can be drawn that the NDWPSO has excellent global search capability, local search capability, and the capability for escaping the local optimal.

In addition, the convergence curves of the 23 benchmark functions are shown in Figs. 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 and 19 . The NDWPSO algorithm has a faster convergence speed in the early stage of the search for processing functions f1-f6, f8-f14, f16, f17, and finds the global optimal solution with a smaller number of iterations. In the remaining benchmark function experiments, the NDWPSO algorithm shows no outstanding performance for convergence speed in the early iterations. There are two reasons of no outstanding performance in the early iterations. On one hand, the fixed-multimodal benchmark function has many disturbances and local optimal solutions in the whole search space. on the other hand, the initialization scheme based on elite opposition-based learning is still stochastic, which leads to the initial position far from the global optimal solution. The inertia weight based on chaotic mapping and the strategy of spiral updating can significantly improve the convergence speed and computational accuracy of the algorithm in the late search stage. Finally, the NDWPSO algorithm can find better solutions than other algorithms in the middle and late stages of the search.

Evolution curve of NDWPSO and other PSO algorithms for f1 (Dim = 30,50,100).

Evolution curve of NDWPSO and other PSO algorithms for f2 (Dim = 30,50,100).

Evolution curve of NDWPSO and other PSO algorithms for f3 (Dim = 30,50,100).

Evolution curve of NDWPSO and other PSO algorithms for f4 (Dim = 30,50,100).

Evolution curve of NDWPSO and other PSO algorithms for f5 (Dim = 30,50,100).

Evolution curve of NDWPSO and other PSO algorithms for f6 (Dim = 30,50,100).

Evolution curve of NDWPSO and other PSO algorithms for f7 (Dim = 30,50,100).

Evolution curve of NDWPSO and other PSO algorithms for f8 (Dim = 30,50,100).

Evolution curve of NDWPSO and other PSO algorithms for f9 (Dim = 30,50,100).

Evolution curve of NDWPSO and other PSO algorithms for f10 (Dim = 30,50,100).

Evolution curve of NDWPSO and other PSO algorithms for f11(Dim = 30,50,100).

Evolution curve of NDWPSO and other PSO algorithms for f12 (Dim = 30,50,100).

Evolution curve of NDWPSO and other PSO algorithms for f13 (Dim = 30,50,100).

Evolution curve of NDWPSO and other PSO algorithms for f14, f15, f16.

Evolution curve of NDWPSO and other PSO algorithms for f17, f18, f19.

Evolution curve of NDWPSO and other PSO algorithms for f20, f21, f22.

Evolution curve of NDWPSO and other PSO algorithms for f23.

To evaluate the performance of different PSO algorithms, a statistical test is conducted. Due to the stochastic nature of the meta-heuristics, it is not enough to compare algorithms based on only the mean and standard deviation values. The optimization results cannot be assumed to obey the normal distribution; thus, it is necessary to judge whether the results of the algorithms differ from each other in a statistically significant way. Here, the Wilcoxon non-parametric statistical test 45 is used to obtain a parameter called p -value to verify whether two sets of solutions are different to a statistically significant extent or not. Generally, it is considered that p  ≤ 0.5 can be considered as a statistically significant superiority of the results. The p -values calculated in Wilcoxon’s rank-sum test comparing NDWPSO and other PSO algorithms are listed in Table  3 for all benchmark functions. The p -values in Table  3 additionally present the superiority of the NDWPSO because all of the p -values are much smaller than 0.5.

In general, the NDWPSO has the fastest convergence rate when finding the global optimum from Figs. 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 and 19 , and thus we can conclude that the NDWPSO is superior to the other PSO variants during the process of optimization.

Comparison experiments between NDWPSO and other intelligent algorithms

Experiments are conducted to compare NDWPSO with several other intelligent algorithms (WOA, HHO, GWO, AOA, EO and DE). The experimental object is 23 benchmark functions, and the experimental parameters of the NDWPSO algorithm are set the same as in Experiment 4.1. The maximum number of iterations of the experiment is increased to 2000 to fully demonstrate the performance of each algorithm. Each algorithm is repeated 30 times individually. The parameters of the relevant intelligent algorithms in the experiments are set as shown in Table 4 . To ensure the fairness of the algorithm comparison, all parameters are concerning the original parameters in the relevant algorithm literature. The experimental results are shown in Tables 5 , 6 , 7 and 8 and Figs. 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 and 36 .

Evolution curve of NDWPSO and other algorithms for f1 (Dim = 30,50,100).

Evolution curve of NDWPSO and other algorithms for f2 (Dim = 30,50,100).

Evolution curve of NDWPSO and other algorithms for f3(Dim = 30,50,100).

Evolution curve of NDWPSO and other algorithms for f4 (Dim = 30,50,100).

Evolution curve of NDWPSO and other algorithms for f5 (Dim = 30,50,100).

Evolution curve of NDWPSO and other algorithms for f6 (Dim = 30,50,100).

Evolution curve of NDWPSO and other algorithms for f7 (Dim = 30,50,100).

Evolution curve of NDWPSO and other algorithms for f8 (Dim = 30,50,100).

Evolution curve of NDWPSO and other algorithms for f9(Dim = 30,50,100).

Evolution curve of NDWPSO and other algorithms for f10 (Dim = 30,50,100).

Evolution curve of NDWPSO and other algorithms for f11 (Dim = 30,50,100).

Evolution curve of NDWPSO and other algorithms for f12 (Dim = 30,50,100).

Evolution curve of NDWPSO and other algorithms for f13 (Dim = 30,50,100).

Evolution curve of NDWPSO and other algorithms for f14, f15, f16.

Evolution curve of NDWPSO and other algorithms for f17, f18, f19.

Evolution curve of NDWPSO and other algorithms for f20, f21, f22.

Evolution curve of NDWPSO and other algorithms for f23.

The experimental data of NDWPSO and other intelligent algorithms for handling 30, 50, and 100-dimensional benchmark functions ( \({f}_{1}-{f}_{13}\) ) are recorded in Tables 8 , 9 and 10 , respectively. The comparison data of fixed-multimodal benchmark tests ( \({f}_{14}-{f}_{23}\) ) are recorded in Table 11 . According to the data in Tables 5 , 6 and 7 , the NDWPSO algorithm obtains 69.2%, 84.6%, and 84.6% of the best results for the benchmark function ( \({f}_{1}-{f}_{13}\) ) in the search space of three dimensions (Dim = 30, 50, 100), respectively. In Table 8 , the NDWPSO algorithm obtains 80% of the optimal solutions in 10 fixed-multimodal benchmark functions.

The convergence curves of each algorithm are shown in Figs. 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 and 36 . The NDWPSO algorithm demonstrates two convergence behaviors when calculating the benchmark functions in 30, 50, and 100-dimensional search spaces. The first behavior is the fast convergence of NDWPSO with a small number of iterations at the beginning of the search. The reason is that the Iterative-mapping strategy and the position update scheme of dynamic weighting are used in the NDWPSO algorithm. This scheme can quickly target the region in the search space where the global optimum is located, and then precisely lock the optimal solution. When NDWPSO processes the functions \({f}_{1}-{f}_{4}\) , and \({f}_{9}-{f}_{11}\) , the behavior can be reflected in the convergence trend of their corresponding curves. The second behavior is that NDWPSO gradually improves the convergence accuracy and rapidly approaches the global optimal in the middle and late stages of the iteration. The NDWPSO algorithm fails to converge quickly in the early iterations, which is possible to prevent the swarm from falling into a local optimal. The behavior can be demonstrated by the convergence trend of the curves when NDWPSO handles the functions \({f}_{6}\) , \({f}_{12}\) , and \({f}_{13}\) , and it also shows that the NDWPSO algorithm has an excellent ability of local search.

Combining the experimental data with the convergence curves, it is concluded that the NDWPSO algorithm has a faster convergence speed, so the effectiveness and global convergence of the NDWPSO algorithm are more outstanding than other intelligent algorithms.

Experiments on classical engineering problems

Three constrained classical engineering design problems (welded beam design, pressure vessel design 43 , and three-bar truss design 38 ) are used to evaluate the NDWPSO algorithm. The experiments are the NDWPSO algorithm and 5 other intelligent algorithms (WOA 36 , HHO, GWO, AOA, EO 41 ). Each algorithm is provided with the maximum number of iterations and population size ( \({\text{Mk}}=500,\mathrm{ n}=40\) ), and then repeats 30 times, independently. The parameters of the algorithms are set the same as in Table 4 . The experimental results of three engineering design problems are recorded in Tables 9 , 10 and 11 in turn. The result data is the average value of the solved data.

Welded beam design

The target of the welded beam design problem is to find the optimal manufacturing cost for the welded beam with the constraints, as shown in Fig.  37 . The constraints are the thickness of the weld seam ( \({\text{h}}\) ), the length of the clamped bar ( \({\text{l}}\) ), the height of the bar ( \({\text{t}}\) ) and the thickness of the bar ( \({\text{b}}\) ). The mathematical formulation of the optimization problem is given as follows:

Welded beam design.

In Table 9 , the NDWPSO, GWO, and EO algorithms obtain the best optimal cost. Besides, the standard deviation (SD) of t NDWPSO is the lowest, which means it has very good results in solving the welded beam design problem.

Pressure vessel design

Kannan and Kramer 43 proposed the pressure vessel design problem as shown in Fig.  38 to minimize the total cost, including the cost of material, forming, and welding. There are four design optimized objects: the thickness of the shell \({T}_{s}\) ; the thickness of the head \({T}_{h}\) ; the inner radius \({\text{R}}\) ; the length of the cylindrical section without considering the head \({\text{L}}\) . The problem includes the objective function and constraints as follows:

Pressure vessel design.

The results in Table 10 show that the NDWPSO algorithm obtains the lowest optimal cost with the same constraints and has the lowest standard deviation compared with other algorithms, which again proves the good performance of NDWPSO in terms of solution accuracy.

Three-bar truss design

This structural design problem 44 is one of the most widely-used case studies as shown in Fig.  39 . There are two main design parameters: the area of the bar1 and 3 ( \({A}_{1}={A}_{3}\) ) and area of bar 2 ( \({A}_{2}\) ). The objective is to minimize the weight of the truss. This problem is subject to several constraints as well: stress, deflection, and buckling constraints. The problem is formulated as follows:

Three-bar truss design.

From Table 11 , NDWPSO obtains the best design solution in this engineering problem and has the smallest standard deviation of the result data. In summary, the NDWPSO can reveal very competitive results compared to other intelligent algorithms.

Conclusions and future works

An improved algorithm named NDWPSO is proposed to enhance the solving speed and improve the computational accuracy at the same time. The improved NDWPSO algorithm incorporates the search ideas of other intelligent algorithms (DE, WOA). Besides, we also proposed some new hybrid strategies to adjust the distribution of algorithm parameters (such as the inertia weight parameter, the acceleration coefficients, the initialization scheme, the position updating equation, and so on).

23 classical benchmark functions: indefinite unimodal (f1-f7), indefinite multimodal (f8-f13), and fixed-dimensional multimodal(f14-f23) are applied to evaluate the effective line and feasibility of the NDWPSO algorithm. Firstly, NDWPSO is compared with PSO, CDWPSO, and SDWPSO. The simulation results can prove the exploitative, exploratory, and local optima avoidance of NDWPSO. Secondly, the NDWPSO algorithm is compared with 5 other intelligent algorithms (WOA, HHO, GWO, AOA, EO). The NDWPSO algorithm also has better performance than other intelligent algorithms. Finally, 3 classical engineering problems are applied to prove that the NDWPSO algorithm shows superior results compared to other algorithms for the constrained engineering optimization problems.

Although the proposed NDWPSO is superior in many computation aspects, there are still some limitations and further improvements are needed. The NDWPSO performs a limit initialize on each particle by the strategy of “elite opposition-based learning”, it takes more computation time before speed update. Besides, the” local optimal jump-out” strategy also brings some random process. How to reduce the random process and how to improve the limit initialize efficiency are the issues that need to be further discussed. In addition, in future work, researchers will try to apply the NDWPSO algorithm to wider fields to solve more complex and diverse optimization problems.

Data availability

The datasets used and/or analyzed during the current study available from the corresponding author on reasonable request.

Sami, F. Optimize electric automation control using artificial intelligence (AI). Optik 271 , 170085 (2022).

Article   ADS   Google Scholar  

Li, X. et al. Prediction of electricity consumption during epidemic period based on improved particle swarm optimization algorithm. Energy Rep. 8 , 437–446 (2022).

Article   Google Scholar  

Sun, B. Adaptive modified ant colony optimization algorithm for global temperature perception of the underground tunnel fire. Case Stud. Therm. Eng. 40 , 102500 (2022).

Bartsch, G. et al. Use of artificial intelligence and machine learning algorithms with gene expression profiling to predict recurrent nonmuscle invasive urothelial carcinoma of the bladder. J. Urol. 195 (2), 493–498 (2016).

Article   PubMed   Google Scholar  

Bao, Z. Secure clustering strategy based on improved particle swarm optimization algorithm in internet of things. Comput. Intell. Neurosci. 2022 , 1–9 (2022).

Google Scholar  

Kennedy, J. & Eberhart, R. Particle swarm optimization. In: Proceedings of ICNN'95-International Conference on Neural Networks . IEEE, 1942–1948 (1995).

Lin, Q. et al. A novel artificial bee colony algorithm with local and global information interaction. Appl. Soft Comput. 62 , 702–735 (2018).

Abed-alguni, B. H. et al. Exploratory cuckoo search for solving single-objective optimization problems. Soft Comput. 25 (15), 10167–10180 (2021).

Brajević, I. A shuffle-based artificial bee colony algorithm for solving integer programming and minimax problems. Mathematics 9 (11), 1211 (2021).

Khan, A. T. et al. Non-linear activated beetle antennae search: A novel technique for non-convex tax-aware portfolio optimization problem. Expert Syst. Appl. 197 , 116631 (2022).

Brajević, I. et al. Hybrid sine cosine algorithm for solving engineering optimization problems. Mathematics 10 (23), 4555 (2022).

Abed-Alguni, B. H., Paul, D. & Hammad, R. Improved Salp swarm algorithm for solving single-objective continuous optimization problems. Appl. Intell. 52 (15), 17217–17236 (2022).

Nadimi-Shahraki, M. H. et al. Binary starling murmuration optimizer algorithm to select effective features from medical data. Appl. Sci. 13 (1), 564 (2022).

Nadimi-Shahraki, M. H. et al. A systematic review of the whale optimization algorithm: Theoretical foundation, improvements, and hybridizations. Archiv. Comput. Methods Eng. 30 (7), 4113–4159 (2023).

Fatahi, A., Nadimi-Shahraki, M. H. & Zamani, H. An improved binary quantum-based avian navigation optimizer algorithm to select effective feature subset from medical data: A COVID-19 case study. J. Bionic Eng. 21 (1), 426–446 (2024).

Abed-alguni, B. H. & AL-Jarah, S. H. IBJA: An improved binary DJaya algorithm for feature selection. J. Comput. Sci. 75 , 102201 (2024).

Yeh, W.-C. A novel boundary swarm optimization method for reliability redundancy allocation problems. Reliab. Eng. Syst. Saf. 192 , 106060 (2019).

Solomon, S., Thulasiraman, P. & Thulasiram, R. Collaborative multi-swarm PSO for task matching using graphics processing units. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation 1563–1570 (2011).

Mukhopadhyay, S. & Banerjee, S. Global optimization of an optical chaotic system by chaotic multi swarm particle swarm optimization. Expert Syst. Appl. 39 (1), 917–924 (2012).

Duan, L. et al. Improved particle swarm optimization algorithm for enhanced coupling of coaxial optical communication laser. Opt. Fiber Technol. 64 , 102559 (2021).

Sun, F., Xu, Z. & Zhang, D. Optimization design of wind turbine blade based on an improved particle swarm optimization algorithm combined with non-gaussian distribution. Adv. Civ. Eng. 2021 , 1–9 (2021).

Liu, M. et al. An improved particle-swarm-optimization algorithm for a prediction model of steel slab temperature. Appl. Sci. 12 (22), 11550 (2022).

Article   MathSciNet   CAS   Google Scholar  

Gad, A. G. Particle swarm optimization algorithm and its applications: A systematic review. Archiv. Comput. Methods Eng. 29 (5), 2531–2561 (2022).

Article   MathSciNet   Google Scholar  

Feng, H. et al. Trajectory control of electro-hydraulic position servo system using improved PSO-PID controller. Autom. Constr. 127 , 103722 (2021).

Chen, Ke., Zhou, F. & Liu, A. Chaotic dynamic weight particle swarm optimization for numerical function optimization. Knowl. Based Syst. 139 , 23–40 (2018).

Bai, B. et al. Reliability prediction-based improved dynamic weight particle swarm optimization and back propagation neural network in engineering systems. Expert Syst. Appl. 177 , 114952 (2021).

Alsaidy, S. A., Abbood, A. D. & Sahib, M. A. Heuristic initialization of PSO task scheduling algorithm in cloud computing. J. King Saud Univ. –Comput. Inf. Sci. 34 (6), 2370–2382 (2022).

Liu, H., Cai, Z. & Wang, Y. Hybridizing particle swarm optimization with differential evolution for constrained numerical and engineering optimization. Appl. Soft Comput. 10 (2), 629–640 (2010).

Deng, W. et al. A novel intelligent diagnosis method using optimal LS-SVM with improved PSO algorithm. Soft Comput. 23 , 2445–2462 (2019).

Huang, M. & Zhen, L. Research on mechanical fault prediction method based on multifeature fusion of vibration sensing data. Sensors 20 (1), 6 (2019).

Article   ADS   PubMed   PubMed Central   Google Scholar  

Wolpert, D. H. & Macready, W. G. No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1 (1), 67–82 (1997).

Gandomi, A. H. et al. Firefly algorithm with chaos. Commun. Nonlinear Sci. Numer. Simul. 18 (1), 89–98 (2013).

Article   ADS   MathSciNet   Google Scholar  

Zhou, Y., Wang, R. & Luo, Q. Elite opposition-based flower pollination algorithm. Neurocomputing 188 , 294–310 (2016).

Li, G., Niu, P. & Xiao, X. Development and investigation of efficient artificial bee colony algorithm for numerical function optimization. Appl. Soft Comput. 12 (1), 320–332 (2012).

Xiong, G. et al. Parameter extraction of solar photovoltaic models by means of a hybrid differential evolution with whale optimization algorithm. Solar Energy 176 , 742–761 (2018).

Mirjalili, S. & Lewis, A. The whale optimization algorithm. Adv. Eng. Softw. 95 , 51–67 (2016).

Yao, X., Liu, Y. & Lin, G. Evolutionary programming made faster. IEEE Trans. Evol. Comput. 3 (2), 82–102 (1999).

Heidari, A. A. et al. Harris hawks optimization: Algorithm and applications. Fut. Gener. Comput. Syst. 97 , 849–872 (2019).

Mirjalili, S., Mirjalili, S. M. & Lewis, A. Grey wolf optimizer. Adv. Eng. Softw. 69 , 46–61 (2014).

Hashim, F. A. et al. Archimedes optimization algorithm: A new metaheuristic algorithm for solving optimization problems. Appl. Intell. 51 , 1531–1551 (2021).

Faramarzi, A. et al. Equilibrium optimizer: A novel optimization algorithm. Knowl. -Based Syst. 191 , 105190 (2020).

Pant, M. et al. Differential evolution: A review of more than two decades of research. Eng. Appl. Artif. Intell. 90 , 103479 (2020).

Coello, C. A. C. Use of a self-adaptive penalty approach for engineering optimization problems. Comput. Ind. 41 (2), 113–127 (2000).

Kannan, B. K. & Kramer, S. N. An augmented lagrange multiplier based method for mixed integer discrete continuous optimization and its applications to mechanical design. J. Mech. Des. 116 , 405–411 (1994).

Derrac, J. et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol. Comput. 1 (1), 3–18 (2011).

Download references

Acknowledgements

This work was supported by Key R&D plan of Shandong Province, China (2021CXGC010207, 2023CXGC01020); First batch of talent research projects of Qilu University of Technology in 2023 (2023RCKY116); Introduction of urgently needed talent projects in Key Supported Regions of Shandong Province; Key Projects of Natural Science Foundation of Shandong Province (ZR2020ME116); the Innovation Ability Improvement Project for Technology-based Small- and Medium-sized Enterprises of Shandong Province (2022TSGC2051, 2023TSGC0024, 2023TSGC0931); National Key R&D Program of China (2019YFB1705002), LiaoNing Revitalization Talents Program (XLYC2002041) and Young Innovative Talents Introduction & Cultivation Program for Colleges and Universities of Shandong Province (Granted by Department of Education of Shandong Province, Sub-Title: Innovative Research Team of High Performance Integrated Device).

Author information

Authors and affiliations.

School of Mechanical and Automotive Engineering, Qilu University of Technology (Shandong Academy of Sciences), Jinan, 250353, China

Jinwei Qiao, Guangyuan Wang, Zhi Yang, Jun Chen & Pengbo Liu

Shandong Institute of Mechanical Design and Research, Jinan, 250353, China

School of Information Science and Engineering, Northeastern University, Shenyang, 110819, China

Xiaochuan Luo

Fushun Supervision Inspection Institute for Special Equipment, Fushun, 113000, China

You can also search for this author in PubMed   Google Scholar

Contributions

Z.Y., J.Q., and G.W. wrote the main manuscript text and prepared all figures and tables. J.C., P.L., K.L., and X.L. were responsible for the data curation and software. All authors reviewed the manuscript.

Corresponding author

Correspondence to Zhi Yang .

Ethics declarations

Competing interests.

The authors declare no competing interests.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary Information

Supplementary information., rights and permissions.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ .

Reprints and permissions

About this article

Cite this article.

Qiao, J., Wang, G., Yang, Z. et al. A hybrid particle swarm optimization algorithm for solving engineering problem. Sci Rep 14 , 8357 (2024). https://doi.org/10.1038/s41598-024-59034-2

Download citation

Received : 11 January 2024

Accepted : 05 April 2024

Published : 10 April 2024

DOI : https://doi.org/10.1038/s41598-024-59034-2

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Particle swarm optimization
• Elite opposition-based learning
• Iterative mapping
• Convergence analysis

By submitting a comment you agree to abide by our Terms and Community Guidelines . If you find something abusive or that does not comply with our terms or guidelines please flag it as inappropriate.

Quick links

• Explore articles by subject
• Guide to authors
• Editorial policies

Sign up for the Nature Briefing newsletter — what matters in science, free to your inbox daily.