© TippaPatt/Shutterstock.com
Dynamic Programming (DP) เป็นส่วนที่มีความต้องการสูงในการเขียนโปรแกรมคอมพิวเตอร์ โดยมีทักษะและเทคนิคเฉพาะสำหรับการแก้ปัญหา ใช่ คุณจะเข้าใจได้ในฐานะวิศวกรซอฟต์แวร์หากไม่มีโปรแกรมนี้ แต่การเขียนโปรแกรมแบบไดนามิกมีแอปพลิเคชันที่สำคัญในโลกแห่งความเป็นจริง และคุณอาจถูกตั้งคำถามในการสัมภาษณ์นักพัฒนาซอฟต์แวร์
หากคุณยังใหม่กับไดนามิก การเขียนโปรแกรมหรือต้องการรีเฟรชทักษะของคุณ บทความสั้นๆ นี้จะอธิบายว่าการเขียนโปรแกรมแบบไดนามิกคืออะไร พร้อมตัวอย่างและตำแหน่งที่คุณสามารถสร้างทักษะ DP ทางออนไลน์ได้
Dynamic Programming คืออะไร
ในการเขียนโปรแกรมคอมพิวเตอร์ Dynamic Programming (DP) เป็นวิธีการแก้ปัญหาที่จัดโครงสร้างและทำให้ปัญหาที่ซับซ้อนง่ายขึ้นโดยการแบ่งปัญหาออกเป็นลำดับย่อยของปัญหาย่อยที่ทับซ้อนกัน ด้วยการใช้ DP ปัญหาหลายคลาสสามารถแก้ไขได้อย่างมีประสิทธิภาพ
DP มีต้นกำเนิดในวิชาคณิตศาสตร์และนำไปใช้ในหลากหลายสาขา ตั้งแต่ชีวสารสนเทศ วิศวกรรมทรัพยากรน้ำ ไปจนถึงเศรษฐศาสตร์
Dynamic Programming ทำงานอย่างไรในวิทยาการคอมพิวเตอร์?
Dynamic Programming ต้องนำไปใช้อย่างเหมาะสมในการเขียนโปรแกรมคอมพิวเตอร์ ปัญหาต้องมีลักษณะสองประการจึงจะเหมาะสมสำหรับ DP:
โครงสร้างพื้นฐานที่เหมาะสมที่สุด: ปัญหาที่ระบุจะมีคุณสมบัติโครงสร้างพื้นฐานที่เหมาะสมที่สุด หากโซลูชันที่เหมาะสมที่สุดสามารถได้มาจากโซลูชันที่เหมาะสมที่สุดของปัญหาย่อย ปัญหาย่อยที่ทับซ้อนกัน: ปัญหาที่เป็นปัญหาควรจะสามารถแยกย่อยออกเป็นลำดับของปัญหาย่อยที่ใช้ซ้ำได้หรืออัลกอริทึมแบบเรียกซ้ำที่สามารถแก้ปัญหาย่อยซ้ำๆ ได้โดยไม่ต้องสร้างปัญหาใหม่
คุณสมบัติทั้งสองนี้เป็นกุญแจสำคัญในการใช้ DP หากพบวิธีแก้ปัญหาที่ดีที่สุดโดยใช้ปัญหาย่อยที่ไม่ทับซ้อนกัน จะไม่สามารถใช้ DP ได้ แต่จะใช้ แบ่งแยกและพิชิตแทน อัลกอริทึมการเรียงลำดับในทำนองเดียวกัน เช่น การเรียงลำดับแบบผสานและการเรียงลำดับแบบรวดเร็ว ไม่ใช่ DP
การเขียนโปรแกรมแบบเรียกซ้ำและไดนามิก
การเรียกซ้ำเป็นกุญแจสำคัญ คุณสมบัติของโครงสร้างพื้นฐานที่เหมาะสมที่สุดที่ใช้ใน DP การเรียกซ้ำเป็นเพียงกระบวนการที่เกิดขึ้นซ้ำๆ เช่น เมื่อคุณยืนอยู่ระหว่างกระจกสองบานและมีการสะท้อนซ้ำแล้วซ้ำอีก (เอฟเฟกต์ Droste)
โครงสร้างย่อยที่เหมาะสมมีลำดับของปัญหาที่แก้ปัญหาได้เองอย่างต่อเนื่องและปัญหาหลักที่เกิดซ้ำ
อัลกอริทึมแบบเรียกซ้ำใน DP จะไม่สร้างปัญหาย่อยใหม่ ทำให้เหลือพื้นที่ว่าง เกิดขึ้นโดยปัญหาย่อยที่ทับซ้อนกันของแต่ละบุคคล ตามหลักการแล้ว ปัญหาย่อยเดียวกันควรได้รับการแก้ไขซ้ำแล้วซ้ำอีก
ประเภทคีย์ของการเขียนโปรแกรมไดนามิก?
DP มี 2 ประเภทหรือเมธอดซึ่งขึ้นอยู่กับวิธีที่คุณจัดการกับปัญหา ทั้งสองวิธีนี้ใช้โซลูชันการท่องจำ การจัดเก็บ และการจัดตารางเพื่อให้สามารถเรียกค้นข้อมูลได้อย่างรวดเร็ว ประหยัดเวลาในการคำนวณซ้ำ
จากบนลงล่าง
ในแนวทางจากบนลงล่าง วิธีแก้ปัญหาเป็นแบบเรียกซ้ำ ทำให้สามารถจดจำวิธีแก้ปัญหาย่อยที่ซ้อนทับกันได้ ปัญหาย่อยใหม่ที่ตามมาจะได้รับการแก้ไขโดยการอ้างอิงแคชข้อมูลที่บันทึกไว้เพื่อดูว่ามีวิธีแก้ปัญหาอยู่แล้วหรือไม่ หากปัญหาย่อยไม่ได้รับการแก้ไขก่อนหน้านี้ ปัญหาย่อยนั้นจะถูกเพิ่มไปยังแคชบันทึกช่วยจำ
DP จากบนลงล่างนั้นง่ายต่อการทำความเข้าใจและใช้งานเนื่องจากช่วยอำนวยความสะดวกในการแก้ปัญหาย่อยตามเป้าหมาย คุณสามารถดีบักได้อย่างง่ายดาย แต่วิธีการเรียกซ้ำนี้สามารถใช้หน่วยความจำแคชจำนวนมาก ซึ่งอาจนำไปสู่ข้อผิดพลาดสแต็กโอเวอร์โฟลว์
จากล่างขึ้นบน
แนวทางจากล่างขึ้นบน หรือที่เรียกว่าการจัดตารางหรือการเติมตาราง ใช้การจัดตารางเพื่อสร้างบันทึกของปัญหาย่อยและแนวทางแก้ไขที่เก็บไว้ จากนั้นจะใช้ปัญหาย่อยที่แก้ไขแล้วเป็นตารางสำหรับการจัดรูปแบบปัญหาจากล่างขึ้นบน ปัญหาย่อยที่เล็กกว่าจะได้รับการแก้ไข โดยโซลูชันจะถูกนำมาใช้เพื่อแก้ปัญหาย่อยที่ใหญ่กว่า สามารถใช้ For loop เพื่อวนซ้ำปัญหาย่อย
ตัวอย่าง: การเขียนโปรแกรมแบบไดนามิกและอนุกรมฟีโบนัชชี
ตัวอย่างที่ใช้งานได้จริงของการเขียนโปรแกรมแบบไดนามิกในการทำงานกับอนุกรมฟีโบนัชชี:
0, 1, 1, 2 , 3, 5, 8, 13, 21, 34, 55…
ด้วยเลขฟีโบนัชชี (Fn) เลขใดๆ ในลำดับคือผลรวมของเลขสองตัวก่อนหน้า เมื่อค่าของ’n’ใน Fn เพิ่มขึ้น ขนาดและความซับซ้อนของการคำนวณตัวเลขเหล่านี้ก็เพิ่มขึ้น
DP สามารถใช้คำนวณเลขฟีโบนัชชีใดๆ ก็ได้ เมื่อใช้ DP คุณไม่จำเป็นต้องสร้างทรีแบบเรียกซ้ำหรือแก้ปัญหาซ้ำแล้วซ้ำอีก เพียงใช้ค่าที่คำนวณไว้ก่อนหน้านี้ ต่อไปนี้คือลักษณะของโค้ดสำหรับการนำซีรีส์นี้ไปใช้โดยใช้วิธีจากบนลงล่าง:
โค้ดที่ใช้คำนวณเลขฟีโบนัชชี
©”TNGD”.com
เหตุใดการเขียนโปรแกรมแบบไดนามิกจึงสำคัญ
การเขียนโปรแกรมแบบไดนามิกไม่ใช่ส่วนที่โดดเด่นของแนวการเขียนโปรแกรมสมัยใหม่ นี่เป็นเพราะปกติแล้วไม่ได้ใช้โดยตรงในการพัฒนาระดับการผลิตร่วมสมัย
วิศวกรที่มีความสามารถหลายคนได้สร้างชื่อเสียงให้กับตัวเองโดยไม่ต้องมีความรู้เกี่ยวกับ DP มากนัก แม้ว่ามันจะเป็นส่วนหนึ่งของภาษาโปรแกรมชั้นนำ เช่น:
PythonJavaScriptRubyPHPPerlLua
ความรู้ด้านการทำงานของ DP นั้นมีค่าสำหรับวิศวกร เพราะสามารถช่วยนักพัฒนาสร้างแอปพลิเคชันซอฟต์แวร์ที่มีโครงสร้างดีขึ้นและมีประสิทธิภาพมากขึ้น
สถาปัตยกรรมบริการที่ใช้ร่วมกันสมัยใหม่ประกอบด้วยแอปพลิเคชันอิสระที่เข้าถึงทรัพยากร (หน่วยความจำ พลังการประมวลผล ความจุของเครือข่าย ค่าใช้จ่าย) ของพูลที่ใช้ร่วมกัน โค้ดที่มีโครงสร้างไม่ดีและขาดความสนใจในการแก้ปัญหาอาจนำไปสู่การใช้ทรัพยากรโดยไม่จำเป็น ส่งผลต่อประสิทธิภาพของแอปพลิเคชันอื่นๆ DP ช่วยในการปรับแต่งโค้ดซอฟต์แวร์เพื่อป้องกันไม่ให้สิ่งนี้เกิดขึ้น
ตัวอย่างการเขียนโปรแกรมแบบไดนามิกในโลกแห่งความเป็นจริง
มีตัวอย่างมากมายของแอปพลิเคชันซอฟต์แวร์ในโลกแห่งความเป็นจริงที่ใช้ DP เพื่อให้มีความว่องไวและมีประสิทธิภาพ และลดความต้องการของระบบสำหรับการเรียกใช้งานให้เหลือน้อยที่สุด ต่อไปนี้เป็นตัวอย่าง:
Google Maps: ใน Google Maps จะใช้ DP เพื่อระบุเส้นทางที่สั้นที่สุดระหว่างจุดเริ่มต้นเดียวและปลายทางต่างๆ เครื่องมือค้นหา: เพื่อคำนวณระดับความคล้ายคลึงกันระหว่างเนื้อหาออนไลน์สองส่วน ซอฟต์แวร์การคัดลอกผลงาน: การพัฒนาอัลกอริธึมระยะห่างของเอกสารเพื่อช่วยตรวจจับระดับความคล้ายคลึงกันระหว่างเอกสารข้อความ เครือข่าย: การถ่ายโอนข้อมูลจากแหล่งเดียวไปยังเครื่องรับหลายเครื่องตามลำดับ เครื่องตรวจการสะกดคำ: อัลกอริทึมระยะแก้ไขที่ใช้เพื่อวัดว่าสองเครื่องต่างกันอย่างไร คำและคำนวณจำนวนการดำเนินการที่จำเป็นในการเปลี่ยนคำหนึ่งเป็นอีกคำหนึ่ง
ฐานข้อมูล/แคชฐานความรู้: ที่จัดเก็บข้อความค้นหา/คำขอทั่วไปในหน่วยความจำหรือแคชในเครื่องที่เข้าถึงได้ DP ช่วยป้องกันการดึงข้อมูลที่ใช้กันทั่วไปซ้ำๆ จากเซิร์ฟเวอร์ เพื่อสนับสนุนการจัดเก็บในเครื่อง
ตัวอย่างคำถามสัมภาษณ์การเขียนโปรแกรมแบบไดนามิก
หากคุณกำลังมองหางานวิศวกรซอฟต์แวร์หรือนักพัฒนาซอฟต์แวร์คนต่อไป ความรู้เกี่ยวกับ DP จะทำให้คุณได้เปรียบในการสัมภาษณ์งาน
DP เป็นเรื่องใหญ่ในการสัมภาษณ์ทางเทคโนโลยี บริษัทเทคโนโลยีชั้นนำอย่าง Google และ Amazon มักจะท้าทายผู้สมัครด้วยคำถาม DP ที่ต้องแก้ไขทันที! นี่คือการทดสอบวิธีคิดของนักพัฒนา และดูว่าพวกเขาจะแยกย่อยงานต่างๆ และหาวิธีที่ใช้ทรัพยากรอย่างคุ้มค่าที่สุดในการแก้ปัญหาหรือไม่
ต่อไปนี้คือตัวอย่างบางส่วนของคำถามและคำตอบในการสัมภาษณ์การเขียนโปรแกรมแบบไดนามิก
นอกเหนือจากสมการฟีโบนัชชีที่แสดงด้านบนแล้ว ต่อไปนี้คือคำถามสัมภาษณ์เกี่ยวกับการเขียนโปรแกรมแบบไดนามิกพร้อมตัวอย่างคำตอบและคำตอบ:
คำถามที่ 1: คุณช่วยอธิบายข้อดีและข้อเสียของ Memoization ได้ไหม
(คำแนะนำ: นี่เป็นคำถามเกี่ยวกับข้อดีและข้อเสียของวิธีการจากบนลงล่างใน DP)
คำตอบ:
ข้อดีของการท่องจำ ได้แก่:
การเขียนโค้ดทำได้ง่ายปัญหาสามารถแก้ไขได้โดยการเขียน wrapper หรือคำอธิบายประกอบที่จะเรียกใช้งานฟังก์ชันเรียกซ้ำโดยอัตโนมัติ คำตอบสามารถหาได้จากแคชและใช้สำหรับปัญหาต่างๆ
ข้อเสียเปรียบหลักของการท่องจำคือถ้าคุณมีจำนวนมากหรือลึก ในการคำนวณ คุณอาจใช้พื้นที่สแต็คหมดอย่างรวดเร็ว
คำถามที่ 2: คุณกำลังไต่อันดับ มาด คุณสามารถปีนขึ้นไปทีละขั้นหรือสองขั้นก็ได้ มีกี่วิธีในการปีนขึ้นไปด้านบน
(คำแนะนำ: คำถามนี้เรียกว่าปัญหา’การปีนบันได’)
คำตอบ: ลองดูที่วิธีการ คำถามสัมภาษณ์การเขียนโค้ดที่พบบ่อยในวิดีโอนี้:
ฉันจะฝึกฝนการเขียนโปรแกรมแบบไดนามิกได้ที่ไหน
การสร้างทักษะในการเขียนโปรแกรมแบบไดนามิกช่วยเสริมทักษะการคิดและการแก้ปัญหาของนักพัฒนา DP ยังสามารถช่วยให้คุณคิดแบบองค์รวมมากขึ้นเกี่ยวกับปัญหาและพัฒนาวิธีแก้ปัญหาที่ผิดปกติแต่มีประสิทธิภาพ หากถึงเวลาที่คุณจะต้องเข้ารับการฝึกอบรมหรือใบรับรองใน DP นี่คือหลักสูตรออนไลน์ที่ดีที่สุด 3 หลักสูตร:
เมื่อคุณเร่งความเร็วแล้ว การฝึกฝนจะทำให้สมบูรณ์แบบ!
การปัดเศษ ขึ้น
การเขียนโปรแกรมแบบไดนามิกอาจไม่ได้เป็นส่วนหนึ่งของกลุ่มนักพัฒนาของคุณ แต่มีความสำคัญต่อองค์กรที่คุณต้องการทำงานด้วย การทำความเข้าใจและการเรียนรู้ DP ไม่เพียงแต่ช่วยให้คุณได้งานทำเท่านั้น แต่ยังปรับปรุงทักษะของคุณและช่วยให้คุณเขียนโค้ดสะอาดที่นักพัฒนาที่เป็นหัวหน้าของคุณจะชื่นชอบ!
Dynamic Programing คืออะไร พร้อมตัวอย่างคำถามที่พบบ่อย (คำถามที่พบบ่อย)
memoization คืออะไร
ในการเขียนโปรแกรม memoization เป็นเทคนิคการเพิ่มประสิทธิภาพที่เก็บผลลัพธ์ของฟังก์ชันที่ใช้ทรัพยากรจำนวนมากไว้ในแคชเพื่อให้สามารถเรียกใช้ได้ ได้อย่างรวดเร็วหากต้องการอีกครั้ง สิ่งนี้ช่วยเพิ่มความเร็วและประสิทธิภาพของโปรแกรมคอมพิวเตอร์
การจัดตารางคืออะไร
การจัดตารางเป็นอีกคำหนึ่งสำหรับวิธีการจากล่างขึ้นบนในการเขียนโปรแกรมแบบไดนามิก ตารางจะเต็มไปด้วยวิธีแก้ปัญหาจากปัญหาย่อยที่ต่ำที่สุดและใช้เพื่อคำนวณคำตอบของปัญหาย่อยในระดับที่สูงขึ้นจนกว่าจะพบวิธีแก้ปัญหาเดิม
การแบ่งแยกและการพิชิตคืออะไร
การแบ่งแยกและการพิชิตเป็นเทคนิคการแก้ปัญหาอีกวิธีหนึ่ง ใช้ปัญหาดั้งเดิมและแยกย่อยออกเป็นปัญหาย่อยที่เกี่ยวข้องกันที่เล็กลงซึ่งสามารถแก้ไขได้โดยอิสระ
การสัมภาษณ์เขียนโค้ดของ Google ยากไหม
ใช่ การสัมภาษณ์เสมือนจริงนี้มีชื่อเสียงว่าเป็นหนึ่งในการสัมภาษณ์ที่ยากที่สุดในภาคเทคโนโลยี คำถามต้องการการค้นคว้าและฝึกฝนอย่างครอบคลุม และโดยทั่วไปจะครอบคลุมหัวข้อที่เกี่ยวข้องกับบริการของ Google คำถาม DP มักถูกถาม
Amazon ถามผู้สมัครงานด้านวิศวกรรมซอฟต์แวร์เกี่ยวกับการเขียนโปรแกรมแบบไดนามิกหรือไม่
ใช่ Amazon ไม่อายที่จะถามคำถามการเขียนโปรแกรมไดนามิกขั้นสูงกับผู้สมัครเพื่อแยกแยะสิ่งที่ไม่ได้เตรียมตัวไว้