Dynamic Programming (Dynamic Programming)

What is Dynamic Programming?

Dynamic Programming algorithms are like Divide and Conquer algorithms in breaking down problems into smaller subproblems and then into smaller subproblems. But unlike dividing to treat, these subproblems are not solved independently. Instead, the results of these subproblems are saved and used for similar subproblems or Overlapping Sub-problems.

We use Dynamic Programming when we have problems that can be divided into similar subproblems, so that their results can be reused. Often these algorithms are used for optimization. Before solving the subproblem, the Dynamic Planning algorithm will try to check the results of the previously solved subproblems. The solutions of subproblems will be combined to get the optimal solution.

Therefore, we can say that:

The original problem should be divided into smaller overlapping sub-problems.

The optimal solution of the problem can be obtained by using the optimal solution of subproblems.

The Dynamic Planning algorithm uses a storage method (Memoization) - that is, we store the solution of the subproblems solved, and if we later need to solve the problem itself then we can take and using calculated results.

Compare

Greedy algorithm and dynamic planning algorithm

Greedy Algorithms is a search algorithm, selecting local optimal solutions in each step in the hope of finding a global optimal solution.

Algorithm Dynamic planning optimizes overlapping subproblems.

Algorithm for division and algorithm Dynamic planning:

Divide and Conquer algorithm is a combination of solutions of subproblems to find the solution of the original problem.

Algorithm Dynamic planning uses the results of subproblems and then tries to optimize the larger problem. Algorithm Dynamic planning uses storage method (Memoization) to remember the results of subproblems solved.

Example of dynamic planning algorithm

Here are some problems that can be solved by using the Dynamic Planning algorithm:

Fibonacci series

Problem of Hanoi Tower (Tower of Hanoi)

Backpack problem

The Dynamic Planning algorithm can be used in both Top-down and Bottom-up methods. And of course, if based on the CPU's working life cycle, the reference to the results of the previous solution is less expensive than solving the problem.

According to Tutorialspoint

Previous article: Algorithm for sharing (divide and conquer)

Next lesson: Theorem mechanic's algorithm (Master Theorem)