พื้นฐานการเขียนโปรแกรมแบบไดนามิก  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อินโฟซิส MAQ
การเขียนโปรแกรมแบบไดนามิก ทฤษฎี

ในพื้นฐานการเขียนโปรแกรมแบบไดนามิกเราจะกล่าวถึงพื้นฐานของ DP และความแตกต่างจากวิธีการโลภการแบ่งและการพิชิตและการเรียกซ้ำ

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

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

ปัญหาพื้นฐานบางประการของ DP  

  • ปัญหาตัวเลขน่าเกลียด
  • เปลี่ยนเหรียญ
  • หมายเลขฟีโบนักชี
  • ปัญหาตัวเลขกระดิ่ง
  • หอคอยฮานอย
  • หมายเลขกระดิ่ง
  • ปัญหาเป้

การเขียนโปรแกรมแบบไดนามิก (DP) เทียบกับวิธีโลภ  

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

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

Dynamic Programming (DP) เทียบกับ Divide & Conquer Method  

ในการแบ่งและพิชิตเราแบ่งปัญหาออกเป็นปัญหาย่อยและแก้ปัญหาย่อยแต่ละปัญหาโดยอิสระ อย่างไรก็ตามใน DP แทนที่จะแก้ปัญหาด้วยตนเองเราจะใช้ผลลัพธ์ที่ได้รับก่อนหน้านี้สำหรับการคำนวณใหม่ กล่าวอีกนัยหนึ่งเราสามารถพูดได้ว่า Divide and Conquer + Memoization = แนวทางไดนามิกจากบนลงล่าง

ดูสิ่งนี้ด้วย
ใช้สแต็กโดยใช้คิวเดียว

(Memoization หมายถึงเทคนิคการจัดเก็บผลลัพธ์ที่คำนวณก่อนหน้านี้โดยทั่วไปใน hash-map เพื่อป้องกันการคำนวณของปัญหาเดิมซ้ำแล้วซ้ำเล่า)

การเขียนโปรแกรมแบบไดนามิก (DP) เทียบกับวิธีการเรียกซ้ำ  

DP จัดเก็บโซลูชันที่คำนวณไว้ก่อนหน้านี้เพื่อใช้เป็นและเมื่อจำเป็นอีกครั้งในอนาคตเพื่อหลีกเลี่ยงการคำนวณซ้ำ อย่างไรก็ตามในการเรียกซ้ำมีความเป็นไปได้ที่จะมีการคำนวณซ้ำซึ่งไม่จำเป็นเนื่องจากไม่ได้เก็บค่าไว้

การเรียกซ้ำนำไปสู่การคำนวณปัญหาซ้ำหลายครั้งดังนั้นในกรณีเช่นนี้ความซับซ้อนของเวลาในการเรียกซ้ำจะมากกว่าโซลูชัน DP เสมอ

ในบทความนี้เรากล่าวถึง การเขียนโปรแกรมแบบไดนามิก พื้นฐาน. ในบทความถัดไปเราจะกล่าวถึงปัญหาพื้นฐานบางประการเกี่ยวกับ DP

อ้างอิง คำถามสัมภาษณ์