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)
You should read it
- Binary Search algorithm (Binary Search)
- Shell Sort in data structure and algorithm
- Alignment algorithm (Merge Sort)
- Quick Sort (Quick Sort)
- Algorithm for sharing (divide and conquer)
- How does YouTube algorithm work?
- Panda 4.0 algorithm was updated by Google on May 20, 2014
- Selection sort algorithm (Selection Sort)
May be interested
- What is Dynamic Island? What effect does Dynamic Island have on iPhone 14 Pro?simply put, dynamic island is the name of the notch on the iphone 14 pro screen and is also the name of the new adaptive feature that apple created.
- Set of multiple choice questions about programming with P10 prizethe programming questions below will give you lots of useful information. if you are interested in learning programming languages, the series of programming language topics will be very helpful for you.
- Set of multiple choice questions about programming with P7 prizecurrent programming is no longer strange to us. programming work is becoming hot and more interested. please join the network administrator to learn about programming skills through multiple-choice questions below.
- Tips for using Dynamic Island on Android smartphonesthere are many applications that support bringing dynamic island to android phones, such as the dynamic spot application. after you set up dynamic spot to work on your android phone, we will see the same black bar display interface as on the iphone.
- Set of multiple-choice questions on award-winning programming P5serializing programming tests, in the following article, readers will be able to expand their knowledge with more interesting questions. let's start.
- Set of multiple choice questions about programming with P6the following network administrators will continue to send you interesting questions about programming. if you love this topic, then try your knowledge.
- P13 programming set of multiple choice questionsyou are a fan of programming languages and want to learn more about this topic. to give you an interesting reading about programming, in this article, the network administrator will send you a good quiz about this topic. invite your reference.
- How to enable Dynamic Lighting on Windows 11windows 11 build 23466 includes an updated dynamic lighting setting. previously, microsoft tested the rgb lighting management inside the settings app.
- Set of multiple choice questions on programming with P3 prizeinvite readers to participate in testing knowledge with questions around the topic of the following programming of network administrator. the question set will have 10 questions with 4 answers, please choose the most accurate answer.
- Set of multiple choice questions on programming with P16 prizemultiple choice questions about programming will be the first piece of knowledge to help you get started with programming. invite your reference.