This article is for those who have heard about and for those who have not heard but want to know more about it. In this article, I will cover all those topics which can help you to work with . Dynamic Programming DP Index: Intro of Dynamic Programming Must have properties for DP!! Implementation of DP Approach of solving a Dynamic Programming Problem Its applications Lets start discussing 🤓. Dynamic Programming ✒️ Intro of Dynamic Programming If you are thinking that Dynamic Programming has any relation with dynamic memory space, then let me correct you. Dynamic Programming has no relation with dynamic memory. So now the question arises, then In simple words, What is a Dynamic Programming? '' Dynamic Programming is an optimized plane recursion, which solves problem in polynomial time (not in exponential as plane recursion does).'' Yes, Dynamic Programming is just an optimization over recursion. The 💡 behind Dynamic Programming is that, if there are some overlapping subproblems (will clear soon), then we can store results of them and reuse that result, if same subproblem needed again. By using this Idea, DP saves time and number of comparisons. idea For those, who don't know what is a plane recursion? Plane recursion is a way of solving problem. In which we break a big problem into smaller subproblems, and then we use result of subproblems for solving big problem. In upcoming topics you will see, that how Dynamic Programming did optimization over plain recursion? So let's move on to next topic! ✒️ Must have properties for DP!! Before we discuss, that how Dynamic Programming does optimization over plain recursion? Let we first see, which type of problems can be solved by DP: 1. Problems with Overlapping Subproblems: As we know, in recursion, we divide a problem into subproblems. And If there are some subproblems present, which we are computing again and again, then it is known as . In Dynamic Programming, we store the result of subproblem at a place ( ), and uses that result instead of calculating again, whenever we need. In this way, we save our valuable time. 😀 Overlapping Subproblems we will see how? For example : If we take an example of , then for 5th Fibonacci number, we computes 3rd Fibonacci 2 times, and 2nd Fibonacci 3 times. finding nth Fibonacci number you see yourself: So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point in storing the solutions if they are not needed again. As recursion also used in many algorithms but we can not use Dynamic Programming there, because those algorithms do not have overlapping subproblems. Divide and Conquer 2. Existence of Optimal Substructure: a problem can have , if its optimal solution can be calculated from optimal solutions of its subproblems. Optimal Substructure Like for Fibonacci number, Optimal Substructure is . As nth Fibonacci number can be calculated with the help of, n-1th and n-2th Fibonacci number. fib(n) = fib(n-1) + fib(n-2) 💡 If you find any problem with these two properties, then that problem can be solved by . Dynamic Programming ✒️ Implementation of DP Under this topic, we will see now that how Dynamic Programming does optimization over plain recursion ? 1. Implementation using Top - Down Approach : This approach is very similar to , with only some modifications. In this we store the result of subproblems in a memo array (or you can use any other structure). Because if we need them again, we can find their values in memo array. Recursion Top - Down approach for nth Fibonacci number problem can be implemented as: { (memo[n] == ) { res; (n == || n == )
        {
            res = n;
        } {
            res = fib(n - , memo) + fib(n - , memo);
        }
        memo[n] = res;
    } memo[n];
} /*
    c++

    optimization of fibonacci numbers implementation
    time comlexity : O(n) rather than exponential ,as in older recursive implementation.
*/ int fib ( n, memo[]) int int if -1 // if we encounter this number first number, as memo[] is initialized with -1 int if 0 1 else 1 2 return By using this approach, for , 3rd Fibonacci will be calculated only 1 time, and next time we will get its value from memo array. Same happens for 2nd Fibonacci. finding 5th Fibonacci number This approach is knowns as Top-Down, because in this we are starting from main problem (top in recursion) and then we are breaking it into subproblems and storing results of its subproblems. This is also known as . Memoization 2. Implementation using Bottom - Up Approach : This approach of implementation is opposite of Top-Down approach, because in this, we do not use recursion. In this approach, we start solving subproblems first ( ), and storing their results in a table ( an array). And in last we calculate the Top problem, using results in table. bottom up manner For Bottom-Up approach can be implemented as: nth Fibonacci number, { table[n + ];
    table[ ] = , table[ ] = ; ( i = ; i <= n; i++)
        table[i] = table[i - ] + table[i - ]; table[n];
} // c++ int fib ( n) int int 1 0 0 1 1 for int 2 1 2 return Dimension of array depends on number of variables we are changing in recursive implementation. If you know recursive implementation of , then you can see that we only change one parameter for every recursive call. That's why we used only one dimensional array. Why we used one dimensional array? nth Fibonacci number 💡 In many problems, we use more than one dimensional array.  for better understanding, you may have a look at my repo ( ). link given in the end* This approach is also known as . As we fill a table in this. Tabulation Dynamic Programming does optimization over plain recursion, by changing implementation approach for the problem. ✒️ Approach of solving a Dynamic Programming Problem Now we have reached on second last topic of this article, 😎. Let we discuss, what should be our Dynamic Programming Problem. approach for solving As Dynamic Programming solutions are faster than exponential brute method, So we should try to think Dynamically for a problem. the first approach for solving a Dynamic Programming Problem, is that we should first identify that the given problem can be solved by Dynamic Programming or not. 1. Identify DP: And by looking for in the given problem. how we can identify this? "must have properties for DP" : second step for solving a Dynamic Programming Problem is, which are the parameters with which we will deal, to solve the problem. 2. Decide parameters decide As in it is the parameter . Fibonacci number, n the third step for solving a Dynamic Programming should be, try to relate the parameter (which we decided in step 2) with different problems. 3. Relate parameters with subproblem : As for 7th Fibonacci number, . This can be like this : . n = 7 fib(n=7) = fib(n=6) + fib(n=5) Basically, try to build optimal substructure. now the last step, for the problem. Either by using or . 4. Code for the problem : write code top-down approach bottom-up approach 💡 So, these are some simple steps that you can follow to solve any Dynamic Programming problem. ✒️ Its applications From perspective, Dynamic Programming has many applications. Because there are many problems present, whose solutions are based on . Some of its applications includes: computer science DP Diff Utility (based on Longest Common Subsequence problem*): This is used to find difference between two files, used in also. Git Resource Allocation (based on 0-1 knapsack problem*) ️Search Closed Words (based on Edit Distance problem*) Floyd war shall algorithm: In this, we find shortest distance between every pair of vertex in graph. Bellman Ford algorithm: used to find shortest distance between source router and destination router. Reach The End! Congrats 👏, you have reached at the end of the article. In this article, we saw an intro of Dynamic Programming, then we saw what properties a problem should have, to be solved by DP. We also saw, what are the different ways to implement DP, and what should be the approach of solving a Dynamic Programming Problem. And in last, we saw some important applications of Dynamic Programming. *If you want to see codes related to Dynamic Programming problem, you may have a look at . this Thank you for reading it till the end 🙂 !

Initialized

How To Design a Tribute Page with Basic HTML5 & CSS3

A Complete Introduction to Graph Data Structure

Connect With Me

Read My Stories

Too Long; Didn't Read

Make resilience your competitive advantage

What Is Dynamic Programming?

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

How To Create CLI Apps

104 Stories To Learn About Go

105 Stories To Learn About Functional Programming

100+ Free Pluralsight Courses to learn Python, Java, and Spring Boot

10 Websites to Learn JavaScript for Beginners

How To Create CLI Apps

104 Stories To Learn About Go

105 Stories To Learn About Functional Programming

100+ Free Pluralsight Courses to learn Python, Java, and Spring Boot

10 Websites to Learn JavaScript for Beginners

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps