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)

Micah Soto

Update 25 May 2019

You should read it

May be interested

Master Theorem algorithm (Master Theorem)
we use the theorem theorem (master theorem) to effectively solve the recursive formulas of the following form.
Linked list data structure (Linked List)
a linked list is a sequence of data structures that are connected through links (links). simply put, the linked list is a data structure consisting of a group of nodes (nodes) forming a string. each node contains data at that node and references the next node in the string.
Data structure of double linked list
the doubly linked list is a variant of the linked list, in which browsing through the buttons can be done in two ways: easy forward and backward. when compared with single link list. here are some important concepts to keep in mind about the double link list.
Data Link List structure (Circular Linked List)
the linked list (circular linked list) is a variant of the linked list, in which the first element points to the last element and the last element points to the first element.
Stack data structure (Stack)
a stack is an abstract data structure (abstract data type - adt for short), mostly used in almost every programming language. name the stack because it acts as a stack in real life, such as a deck of cards or a stack of disks ...
Queue data structure (Queue)
queue (queue) is an abstract data structure, is something similar to queues in everyday life (queuing).