Summarise provided text and transform it into cards. Every card should contain a question and a short answer.

Dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems.

Dynamic programming is used where we have problems, which can be divided into similar sub-problems, so that their results can be re-used. Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, dynamic algorithm will try to examine the results of the previously solved sub-problems. The solutions of sub-problems are combined in order to achieve the best solution.

So we can say that −

The problem should be able to be divided into smaller overlapping sub-problem.

An optimum solution can be achieved by using an optimum solution of smaller sub-problems.

Dynamic algorithms use Memoization.

Comparison
In contrast to greedy algorithms, where local optimization is addressed, dynamic algorithms are motivated for an overall optimization of the problem.

In contrast to divide and conquer algorithms, where solutions are combined to achieve an overall solution, dynamic algorithms use the output of a smaller sub-problem and then try to optimize a bigger sub-problem. Dynamic algorithms use Memoization to remember the output of already solved sub-problems.

Example
The following computer problems can be solved using dynamic programming approach −

Fibonacci number series
Knapsack problem
Tower of Hanoi
All pair shortest path by Floyd-Warshall
Shortest path by Dijkstra
Project scheduling
Dynamic programming can be used in both top-down and bottom-up manner. And of course, most of the times, referring to the previous solution output is cheaper than recomputing in terms of CPU cycles.
สรุปข้อความที่ให้มาและแปลงเป็นการ์ด การ์ดทุกใบควรมีคำถามและคำตอบสั้นๆ วิธีการเขียนโปรแกรมแบบไดนามิกนั้นคล้ายคลึงกับการแบ่งและพิชิตโดยแยกย่อยปัญหาออกให้เล็กลงแต่ยังเล็กลงอีกด้วย แต่ปัญหาย่อยเหล่านี้ต่างจากการแบ่งแยกและพิชิตตรงที่ไม่ได้รับการแก้ไขอย่างเป็นอิสระ แต่ผลลัพธ์ของปัญหาย่อยเล็กๆ น้อยๆ เหล่านี้จะถูกจดจำและใช้สำหรับปัญหาย่อยที่คล้ายกันหรือทับซ้อนกัน การเขียนโปรแกรมแบบไดนามิกจะใช้เมื่อเรามีปัญหาซึ่งสามารถแบ่งออกเป็นปัญหาย่อยที่คล้ายกันเพื่อให้ผลลัพธ์สามารถนำกลับมาใช้ใหม่ได้ โดยส่วนใหญ่ อัลกอริธึมเหล่านี้ใช้สำหรับการปรับให้เหมาะสม ก่อนที่จะแก้ไขปัญหาย่อยในมือ อัลกอริธึมไดนามิกจะพยายามตรวจสอบผลลัพธ์ของปัญหาย่อยที่ได้รับการแก้ไขก่อนหน้านี้ การแก้ปัญหาย่อยจะถูกนำมารวมกันเพื่อให้ได้ทางออกที่ดีที่สุด ดังนั้นเราจึงสามารถพูดได้ว่า - ปัญหาควรจะสามารถแบ่งออกเป็นปัญหาย่อยที่ทับซ้อนกันที่มีขนาดเล็กกว่าได้ วิธีแก้ปัญหาที่เหมาะสมที่สุดสามารถทำได้โดยการใช้วิธีแก้ปัญหาย่อยที่เหมาะสมที่สุด อัลกอริธึมแบบไดนามิกใช้การจดจำ การเปรียบเทียบ ตรงกันข้ามกับอัลกอริธึมโลภ ที่ซึ่งการเพิ่มประสิทธิภาพเฉพาะที่ได้รับการแก้ไข อัลกอริธึมแบบไดนามิกได้รับการกระตุ้นให้เพิ่มประสิทธิภาพโดยรวมของปัญหา ตรงกันข้ามกับการแบ่งและพิชิตอัลกอริธึม โดยที่โซลูชันถูกรวมเข้าด้วยกันเพื่อให้ได้โซลูชันโดยรวม อัลกอริธึมแบบไดนามิกจะใช้ผลลัพธ์ของปัญหาย่อยที่เล็กกว่า จากนั้นพยายามปรับปัญหาย่อยที่ใหญ่กว่าให้เหมาะสม อัลกอริธึมแบบไดนามิกใช้ Memoization เพื่อจดจำผลลัพธ์ของปัญหาย่อยที่แก้ไขแล้ว ตัวอย่าง ปัญหาคอมพิวเตอร์ต่อไปนี้สามารถแก้ไขได้โดยใช้แนวทางการเขียนโปรแกรมแบบไดนามิก - ชุดหมายเลขฟีโบนัชชี ปัญหากระเป๋าเป้สะพายหลัง หอคอยแห่งฮานอย ทุกคู่เส้นทางที่สั้นที่สุดโดย Floyd-Warshall เส้นทางที่สั้นที่สุดโดย Dijkstra การตั้งเวลาโครงการ การเขียนโปรแกรมแบบไดนามิกสามารถใช้ได้ทั้งในลักษณะบนลงล่างและจากล่างขึ้นบน . และแน่นอนว่า โดยส่วนใหญ่แล้ว การอ้างถึงผลลัพธ์ของโซลูชันก่อนหน้านี้จะมีราคาถูกกว่าการคำนวณใหม่ในแง่ของรอบของ CPU
spam lang_mismatch pii not_appropriate hate_speech sexual_content quality toxicity humor creativity violence