Dynamic programming is the optimization of recursive solutions. When there is a program where recursion takes place where there is a repeated input, dynamic programming can help reduce the run time instead of having to go through the recursive process. It uses the idea of storing outputs of the sub-problems in case they are repeated so that recomputing need not take place. The use of optimization in dynamic programming can reduce the time complexity from an exponential function to a polynomial time.
For example, in the Fibonacci sequence program, if we use dynamic programming instead of recursive programming, the time complexity becomes linear instead of exponential.
Dynamic programming is used in many famous programs such as the Gold Mine problem, the 0-1 Knapsack problem, the Golomb sequence, the Subset Sum problem, and nth Catalan Number, among many others.
Essentially, dynamic programming does the following:
The problem should be divided into sub-problems.
Each sub-problem is solved to create multiple small solutions.
These solutions are put together to solve the main problem.
Dynamic programming allows the prevention of repetition of function recalls when the required output has already been computed. It retrieves the output from the memory.
Dynamic algorithms use Memoization, which means that the previous results are stored in a table, from where they can easily be accessed without having to run the whole algorithm again.
Compared to divide and conquer algorithms, where the solutions are combined to achieve the final main solution, dynamic algorithms use the stored outputs of a smaller sub-problem and then optimize a bigger sub-problem.
As previously mentioned, dynamic programming uses memoization. Memoization is a technique to improve the performance of recursive algorithms. It is when the recursive algorithm is rewritten so that any previous solutions are stored in a table (or arrays). When the function needs to be called again, it can search for the previous solution in the array first instead of having to rerun the method every time.
Advantages of Dynamic Programming
It is very suitable for multi-stage, sequential, or multi-point decision processes.
It is suitable for linear or non-linear problems, discrete or continuous variables, and deterministic problems.
Disadvantages of Dynamic Programming
There is no general formation of dynamic programming that is currently available. Every problem needs to be solved using a unique way.
By dividing a problem into multiple sub-problems and constantly storing the intermediate results consumes a lot of storage space.
Article was written for CyberClubNPSi
コメント