ผลรวมพาธต่ำสุดเมื่อมีสิ่งกีดขวาง
ส่งต่อต้นทุนที่ดีที่สุดผ่านแต่ละเซลล์
ผลรวมพาธต่ำสุดเมื่อมีสิ่งกีดขวาง เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
จากการนับสู่การคำนวณต้นทุน
ตอนนี้แต่ละเซลล์มีค่า และคุณต้องการหาเส้นทางที่มีต้นทุนต่ำที่สุดไปยังมุมตาราง เป้าหมายเปลี่ยนจากการนับเส้นทางเป็นการลดต้นทุนให้ต่ำที่สุด
กำหนดสถานะ
ให้ dp[i][j] เป็นต้นทุนรวมที่น้อยที่สุดในการไปถึงเซลล์ (i, j) ใช้ตารางและการเคลื่อนที่แบบเดิม แต่ติดตามผลรวมแทนจำนวนวิธี
การเปลี่ยนสถานะ
คุณเลือกเพื่อนบ้านขาเข้าที่มีต้นทุนต่ำกว่าจากสองทาง แล้วบวกค่าของเซลล์ปัจจุบัน การเลือกค่าต่ำสุดนี้คือหัวใจของสมการเวียนเกิด
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])ทำเครื่องหมายสิ่งกีดขวาง
สิ่งกีดขวางคือเซลล์ที่คุณไม่สามารถอยู่บนเซลล์นั้นได้ กำหนดต้นทุนเป็นอนันต์ เพื่อให้เส้นทางใดก็ตามที่ผ่านเซลล์นี้ไม่มีทางเป็นเส้นทางที่มีต้นทุนต่ำสุด
INF = float('inf')ปิดกั้นอย่างเป็นระเบียบ
เมื่อในตารางระบุว่าเซลล์หนึ่งถูกปิดกั้น ให้กำหนดค่า dp ของเซลล์นั้นเป็นอนันต์แล้วไปต่อ ขั้นตอนการหาค่าต่ำสุดจะหลีกเลี่ยงเซลล์นั้นเอง
if blocked(i, j):
dp[i][j] = INF
continueตรวจสอบจุดเริ่มต้น
หากเซลล์เริ่มต้นถูกปิดกั้น จะไม่มีเส้นทางใดเลย ตรวจสอบเรื่องนี้เป็นอันดับแรกเพื่อไม่ให้คืนค่าต้นทุนที่ไม่ถูกต้อง
กำหนดค่าเซลล์แรก
เซลล์เริ่มต้นไม่มีเพื่อนบ้านที่ใช้เดินทางมาได้ ดังนั้นต้นทุนของเซลล์นี้จึงเป็นเพียงค่าของตัวมันเอง กำหนดค่า dp[0][0] ก่อนเริ่มลูป
dp[0][0] = grid[0][0]จัดการขอบตาราง
แถวบนสุดรับค่าได้จากทางซ้ายเท่านั้น ส่วนคอลัมน์ซ้ายสุดรับค่าได้จากด้านบนเท่านั้น จัดการขอบตารางเหล่านี้เพื่อไม่ให้อ่านค่านอกตาราง
อนันต์ส่งต่อไปเรื่อย ๆ
เมื่อบวกค่าใด ๆ กับอนันต์ ผลลัพธ์ยังคงเป็นอนันต์ ดังนั้นเซลล์ที่ถูกล้อมจนเข้าไม่ถึงจะยังคงมีต้นทุนเป็น INF เซลล์ที่ไปไม่ถึงจะแสดงสถานะของตนเองโดยอัตโนมัติ
อ่านผลลัพธ์
ต้นทุนต่ำสุดจะอยู่ที่เซลล์มุมขวาล่าง หากค่านั้นยังเป็นอนันต์ แสดงว่าไม่มีเส้นทางที่ใช้ได้เลย
ans = dp[m-1][n-1]
if ans == INF:
ans = -1เมื่อวิธีละโมบใช้ไม่ได้
การก้าวไปหาเพื่อนบ้านที่มีค่าน้อยกว่าเสมออาจทำให้คุณติดกับดัก มีเพียง DP แบบเต็มเท่านั้นที่รับประกันเส้นทางที่มีต้นทุนต่ำสุดโดยรวม ไม่ใช่การมองแบบละโมบเพียงระยะสั้น
ตรวจสอบความเข้าใจ
คุณจะทำให้ DP สำหรับเส้นทางหลีกเลี่ยงเซลล์ที่ถูกปิดกั้นได้อย่างไร โดยไม่ต้องเขียนกรณีพิเศษให้เพื่อนบ้านทุกเซลล์
สรุปทบทวน: เส้นทางต้นทุนต่ำสุดที่มีสิ่งกีดขวาง
เลือกเพื่อนบ้านที่มีต้นทุนต่ำกว่าแล้วบวกค่าของเซลล์ กำหนดเซลล์ที่ถูกปิดกั้นเป็นอนันต์ แล้วอ่านค่าที่มุมตาราง หากมุมตารางเป็น INF หมายถึงไม่มีเส้นทาง 🧱
คำถามที่พบบ่อย
บทเรียน “ผลรวมพาธต่ำสุดเมื่อมีสิ่งกีดขวาง” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ผลรวมพาธต่ำสุดเมื่อมีสิ่งกีดขวาง” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ผลรวมพาธต่ำสุดเมื่อมีสิ่งกีดขวาง”
ส่งต่อต้นทุนที่ดีที่สุดผ่านแต่ละเซลล์ คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “ผลรวมพาธต่ำสุดเมื่อมีสิ่งกีดขวาง” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การนับพาธบนกริด
- ผลรวมพาธต่ำสุดเมื่อมีสิ่งกีดขวาง
- ลำดับร่วมที่ยาวที่สุด
- ระยะห่างการแก้ไขทีละขั้น