การนับพาธบนกริด
รวมจำนวนพาธจากมุมหนึ่งไปยังอีกมุมหนึ่ง
การนับพาธบนกริด เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
ปัญหาตารางแบบคลาสสิก
คุณเริ่มจากมุมซ้ายบนของตารางและต้องการไปยังมุมขวาล่าง แต่ละก้าวเคลื่อนไปทางขวาหรือลงด้านล่าง จะมีเส้นทางที่แตกต่างกันทั้งหมดกี่เส้นทาง
เหตุผลที่ DP เหมาะสม
แต่ละเซลล์สามารถไปถึงได้จากเซลล์ด้านบนหรือเซลล์ทางซ้าย การมีส่วนซ้ำกันนี้เองคือเหตุผลที่ปัญหานี้เหมาะกับ DP
กำหนดสถานะ
ให้ dp[i][j] เป็นจำนวนวิธีไปถึงเซลล์ (i, j) จากจุดเริ่มต้น การตั้งชื่อสถานะให้ชัดเจนถือเป็นครึ่งหนึ่งของการแก้ปัญหา
การเปลี่ยนสถานะ
คุณมาถึงเซลล์หนึ่งได้จากด้านบนหรือด้านซ้ายเท่านั้น ดังนั้นจำนวนวิธีจึงเป็นผลรวมของทั้งสองทาง นี่คือการเปลี่ยนสถานะที่ขับเคลื่อนตารางทั้งหมด
dp[i][j] = dp[i-1][j] + dp[i][j-1]กรณีฐาน
เซลล์เริ่มต้นมีวิธีไปถึงเพียงหนึ่งวิธี นั่นคือไม่ต้องทำอะไร ดังนั้น dp[0][0] จึงมีค่าเป็น 1 ก่อนเติมค่าอื่นใด
dp[0][0] = 1ขอบตารางมีเส้นทางเดียว
เซลล์ในแถวบนสุดหรือคอลัมน์ซ้ายสุดมีเส้นทางตรงเพียงเส้นเดียว จำนวนของเซลล์เหล่านั้นจึงเป็น 1 เสมอ เนื่องจากเพื่อนบ้านอีกด้านอยู่นอกตาราง
สร้างตาราง
สร้างตารางขนาด m คูณ n แล้วเติมศูนย์ไว้ การกำหนดขนาดล่วงหน้าช่วยให้การใช้ดัชนีเป็นระเบียบและหลีกเลี่ยงปัญหาที่ไม่คาดคิด
dp = [[0] * n for _ in range(m)]เติมค่าตามลำดับการอ่าน
วนผ่านแถวก่อนแล้วจึงผ่านคอลัมน์ จากบนลงล่างและจากซ้ายไปขวา ลำดับนี้รับประกันว่าเพื่อนบ้านทั้งสองจะพร้อมก่อนที่คุณจะนำมาใช้
for i in range(m):
for j in range(n):
...เซลล์คำตอบ
เมื่อเติมค่าครบแล้ว จำนวนเส้นทางจะอยู่ในเซลล์สุดท้าย คำตอบคือ dp[m-1][n-1] ซึ่งอยู่ที่มุมขวาล่าง
answer = dp[m-1][n-1]ประหยัดหน่วยความจำด้วยแถวเดียว
แต่ละแถวต้องใช้เพียงแถวที่อยู่เหนือขึ้นไป ดังนั้นคุณสามารถเก็บไว้เพียงแถวเดียวและอัปเดตค่าในตำแหน่งเดิมได้ วิธีนี้ลดการใช้หน่วยความจำเหลือ O(n)
row[j] += row[j-1]ทางลัดทางคณิตศาสตร์
เมื่อไม่มีสิ่งกีดขวาง คำตอบคือสัมประสิทธิ์ทวินาม โดยเลือกว่าจากจำนวนก้าวทั้งหมด ก้าวใดจะลงด้านล่าง แต่เมื่อมีสิ่งกีดขวาง DP ยังคงมีประสิทธิภาพกว่า
ตรวจสอบความเข้าใจ
คุณกำลังเติมค่า dp[i][j] ให้เซลล์ด้านในที่เปิดอยู่ สูตรใดถูกต้อง
สรุปทบทวน: การนับเส้นทาง
กำหนด dp ให้เป็นจำนวนเส้นทางไปยังเซลล์หนึ่ง ตั้งค่า dp[0][0] เป็น 1 แล้วบวกค่าเซลล์ด้านบนกับเซลล์ด้านซ้าย มุมตารางจะเก็บคำตอบของคุณไว้ 🧭
คำถามที่พบบ่อย
บทเรียน “การนับพาธบนกริด” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การนับพาธบนกริด” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การนับพาธบนกริด”
รวมจำนวนพาธจากมุมหนึ่งไปยังอีกมุมหนึ่ง คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “การนับพาธบนกริด” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ