Dynamic Programming: Elevating Efficient Solutions

Introduction 

Dynamic programming is a way to optimise problems and is used in computer science extensively to solve bigger problems by breaking them into smaller overlapping subproblems that can be solved independently.This method is extremely useful for problems that tend to have an optimal substructure and subproblems which overlap,and identify as the key characteristics of dynamic programming problems.

This article is an attempt to break down the complex concepts of dynamic programming to help you solve problems on your own with ease. 

Difference between Greedy Algorithms and Dynamic Programming

Dynamic Programming

1. It fol bottom up approach that tries to build up the solution by solving the subproblems and obtaining their solutions.
2. It is useful for solving problems where the optimal solution is obtained and is a result of a combination of subproblems.
3. It stores the solutions of subproblems and reuses them to avoid obtaining solutions to the same subproblems again and again.
4. It is generally not as fast as greedy and is more complex than the same but it guarantees that an optimal solution will be obtained.

Greedy Algorithms

1. It makes locally optimised choices at each step and tries to obtain an optimum.
2. It is useful for solving problems where making such choices at each step can help obtain an optimal solution.
3. It does not consider the consequences of the decision taken at each step.
4. It is generally simpler and less complicated than dynamic programming.

Code Example of a Dynamic Programming Problem

Dynamic program uses imagination along with recursion. Recursion allows one to express the value of a function in terms of other values obtained from the same function. Imagination and consideration of edge cases allows one to know how overlapping subproblems lead to wastage of memory and resources. The crux of this technique is that it stores the solutions of the subproblems which can be accessed later.

Let’s find the fibonacci of a number using dynamic programming and then compare it with recursion. A fibonacci sequence is formed by obtaining each term as a sum of its previous two terms.

Recursive Solution

Recursion also focuses on solving the subproblems and those subproblems and their division can be shown using a recursion tree. However, this solution consumes a lot of memory and resources since the solutions for the overlapping subproblems are not stored.

int fibonacci(int n) 
 {        
if (n < 2)            
return 1;        
return fibonacci(n-1) + fibonacci(n-2);    
 }

Dynamic Programming Solution

The above code does promise a solution but it is not an optimised way as it can waste memory when calculated for large numbers. In this way we can calculate each unique quantity only once and obtain an optimal solution.

void fibonacci() 
   {        
fib[0] = 1;        
fib[1] = 1;        
for (int t = 2; t<n; t++)           
fib[t] = fib[t-1] + fib[t-2]; 
   }

Popular Dynamic Programming Problems

Dynamic Programming is one of the toughest concepts to master while preparing for job interviews question but is also quite important at the same time. Given below are some important problems which have been gathered from various platforms. 

Here is how you can approach a dynamic programming problem:

1. Identify how the problem can be broken down.
2. Try to form a recurrence relation and apply recursion.
3. Identify the base cases.
4. It can be applied both recursively and iteratively and has to be decided according to one’s ease.
5. Add memoization technique.
6. Calculate the time complexity.

Some popular dynamic programming problems are given as under:

1. Climbing Stairs: This is one of the most essential problems which uses it. In this problem, one has to calculate distinct ways to reach the nth step. Each time you can climb 1 or 2 steps.
2. Knapsack Problem: In this problem, one is provided with weights and profits of n items, and it is constrained using a capacity c. The goal is to get maximum profit from items in the knapsack while being wary of the capacity constraint.
3. Edit Distance Problem: This is one of the easier problems to solve using a dynamic programming approach. In this question, two words are provided, and one has to calculate the minimum number of operations to convert word A to word B.
4. Longest Palindromic Subsequence: This question involves a sequence for which the length of the longest palindromic subsequence has to be found.Palindrome elements read the same backward and forward alike. Subsequence is a sequence that is derived from the sequence by removing some elements  Or no elements without changing the order of the remaining elements.
5. Longest Common Substring: Given two strings s1 and s2,and the length of longest common substring among them has to be found.

Conclusion

In conclusion, the comparison between recursion and dynamic programming highlights the repetitive nature of calculating solutions in recursion, while It focuses on optimising subproblems and storing their solutions to eliminate redundancy. Breaking down extensive problems into manageable subparts allows computers to efficiently apply mathematical algorithms and determine optimal solutions.

It emerges as a valuable method for problem-solving by finding the shortest path to a solution. Whether adopting a top-down approach, which dissects problems into smaller components and solves them incrementally, or a bottom-up strategy, which progresses towards the equation with the highest obtained value, It provides a versatile and effective framework for tackling complex problems.

FAQ’s

Read Some Latest Blogs

• 
  Data Science vs Data Analytics: Top Key Differences for Success
• 
  How To Become A Data Scientist In India?: Achieve Your Data Scientist Dreams
• 
  What are Callback Function in JavaScript?: A Guide to Effective Implementation
• 
  Top 9 Interview Questions and Answers for Freshers Success
• 
  What Is Python and Its Dynamic Uses?