การเขียนโปรแกรมแบบไดนามิกคืออะไร?

การเขียนโปรแกรมแบบไดนามิกเมื่ออ้างถึงสาขาวิทยาศาสตร์คอมพิวเตอร์อธิบายกลุ่มของอัลกอริทึมคอมพิวเตอร์ที่คล้ายกันหมายถึงการแก้ปัญหาที่ซับซ้อนโดยการทำลายปัญหาลงในชุดของปัญหาที่เล็กลงสร้างขึ้นครั้งแรกโดย Richard Bellman ในปี 1950 การเขียนโปรแกรมแบบไดนามิกทำงานกับปัญหาที่ทับซ้อนย่อยหรือโครงสร้างย่อยที่ดีที่สุดเพื่อให้เข้าใจว่าการเขียนโปรแกรมแบบไดนามิกทำงานได้ดีที่สุดที่จะเข้าใจแนวคิดที่อยู่เบื้องหลังคำศัพท์ทั้งสองนี้

subproblems ที่ทับซ้อนกันจะอธิบายสมการที่ซับซ้อนซึ่งเมื่อแบ่งออกเป็นสมการขนาดเล็ก ๆ ให้ใช้สมการส่วนเล็ก ๆ ของสมการที่เล็กกว่าหนึ่งครั้งตัวอย่างเช่นสมการทางคณิตศาสตร์บอกให้คำนวณผลลัพธ์ที่เป็นไปได้ทั้งหมดโดยใช้ชุดตัวเลขอาจคำนวณผลลัพธ์เดียวกันหลายครั้งในขณะที่คำนวณผลลัพธ์อื่น ๆ เพียงครั้งเดียวการเขียนโปรแกรมแบบไดนามิกจะบอกปัญหานี้ว่าหลังจากคำนวณผลลัพธ์ในครั้งแรกที่ควรบันทึกผลลัพธ์นั้นและเสียบคำตอบเข้ากับสมการในภายหลังแทนที่จะคำนวณอีกครั้งเมื่อจัดการกับกระบวนการและสมการที่ซับซ้อนยาว ๆ สิ่งนี้จะช่วยประหยัดเวลาและสร้างโซลูชันที่เร็วขึ้นโดยใช้ขั้นตอนน้อยลง

โครงสร้างย่อยที่ดีที่สุดสร้างโซลูชันโดยการค้นหาคำตอบที่ดีที่สุดสำหรับปัญหาย่อยทั้งหมดจากนั้นสร้างคำตอบโดยรวมที่ดีที่สุดหลังจากทำลายปัญหาที่ซับซ้อนออกเป็นปัญหาที่น้อยลงคอมพิวเตอร์จะใช้ระบบคณิตศาสตร์เพื่อกำหนดว่าคำตอบที่ดีที่สุดสำหรับแต่ละปัญหาคืออะไรมันคำนวณคำตอบสำหรับปัญหาดั้งเดิมจากคำตอบที่เล็กกว่าข้อบกพร่องมีอยู่กับกระบวนการนี้ในขณะที่มันให้วิธีการแก้ปัญหาที่ใช้งานได้ดีที่สุดทางคณิตศาสตร์ แต่อาจหรือไม่ใช่วิธีแก้ปัญหาที่ดีที่สุดในชีวิตจริงขึ้นอยู่กับประเภทของปัญหาและวิธีที่เกี่ยวข้องกับโลกแห่งความเป็นจริง

ในระหว่างการดำเนินการใด ๆ เหล่านี้การเขียนโปรแกรมแบบไดนามิกอัลกอริทึมพยายามค้นหาเส้นทางที่สั้นที่สุดในการแก้ปัญหาอาจใช้เวลาหนึ่งในสองวิธีในการทำเช่นนี้วิธีการจากบนลงล่างแบ่งสมการลงในสมการที่เล็กลงและนำคำตอบกลับมาใช้ใหม่สำหรับสมการเหล่านี้เมื่อจำเป็นวิธีการจากล่างขึ้นบนพยายามที่จะแก้ไขค่าทางคณิตศาสตร์ที่เล็กที่สุดหลังจากทำลายสมการลงแล้วทำงานขึ้นไปสู่ที่ใหญ่ที่สุดจากที่นั่นทั้งสองวิธีประหยัดเวลา แต่การเขียนโปรแกรมแบบไดนามิกจะทำงานได้ก็ต่อเมื่อปัญหาดั้งเดิมสามารถแบ่งออกเป็นสมการขนาดเล็กซึ่งในบางจุดจะถูกนำกลับมาใช้ใหม่เพื่อแก้สมการ