Characteristics of Dynamic Programming Algorithm
- In general, dynamic programming (DP) is one of the most powerful techniques for solving a certain class of problems.
- There is an elegant way to formulate the approach and a very simple thinking process, and the coding part is very easy.
- Essentially, it is a simple idea, after solving a problem with a given input, save the result as a reference for future use, so you won’t have to re-solve it.. briefly ‘Remember your Past’ :).
- It is a big hint for DP if the given problem can be broken up into smaller sub-problems, and these smaller subproblems can be divided into still smaller ones, and in this process, you see some overlapping subproblems.
- Additionally, the optimal solutions to the subproblems contribute to the optimal solution of the given problem (referred to as the Optimal Substructure Property).
- The solutions to the subproblems are stored in a table or array (memoization) or in a bottom-up manner (tabulation) to avoid redundant computation.
- The solution to the problem can be constructed from the solutions to the subproblems.
- Dynamic programming can be implemented using a recursive algorithm, where the solutions to subproblems are found recursively, or using an iterative algorithm, where the solutions are found by working through the subproblems in a specific order.
Dynamic programming works on following principles:
- Characterize structure of optimal solution, i.e. build a mathematical model of the solution.
- Recursively define the value of the optimal solution.
- Using bottom-up approach, compute the value of the optimal solution for each possible subproblems.
- Construct optimal solution for the original problem using information computed in the previous step.
Applications:
Dynamic programming is used to solve optimization problems. It is used to solve many real-life problems such as,
(i) Make a change problem
(ii) Knapsack problem
(iii) Optimal binary search tree
Dynamic Programming (DP) Tutorial with Problems
Dynamic Programming (DP) is defined as a technique that solves some particular type of problems in Polynomial Time. Dynamic Programming solutions are faster than the exponential brute method and can be easily proved their correctness.
Important Topics in Dynamic Programming Tutorial
- Characteristics of Dynamic Programming Algorithm:
- What is the difference between a Dynamic programming algorithm and recursion?
- Techniques to solve Dynamic Programming Problems:
- Tabulation(Dynamic Programming) vs Memoization:
- How to solve a Dynamic Programming Problem?
- How to solve Dynamic Programming problems through Example?
- Greedy approach vs Dynamic programming
- Some commonly asked problems in Dynamic programming:
- FAQs about Dynamic Programming Algorithm:
Dynamic Programming is mainly an optimization over plain recursion. 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. This simple optimization reduces time complexities from exponential to polynomial.
Introduction to Dynamic Programming – Data Structures and Algorithm Tutorials
Contact Us