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

คำชี้แจงปัญหา: คำนวณจำนวนเส้นทางในตาราง nxn จากมุมซ้ายบนไปยังมุมขวาล่าง เพื่อให้เส้นทางไปเยี่ยมชมแต่ละช่องสี่เหลี่ยมจัตุรัสหนึ่งครั้ง ตัวอย่างเช่น ในตาราง 7£7 มีเส้นทางดังกล่าว 111,712 เส้นทาง

อัลกอริธึมและการเพิ่มประสิทธิภาพ: เราเริ่มต้นด้วยอัลกอริธึมย้อนรอยที่ตรงไปตรงมา จากนั้นจึงปรับให้เหมาะสมทีละขั้นตอนโดยใช้การสังเกตวิธีการตัดการค้นหา

นี่คือส่วนที่ฉันไม่เข้าใจ:

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

ฉันเข้าใจว่ามันจะมีคำตอบสมมาตร เราก็หาได้ครึ่งหนึ่งแล้วคูณตัวเลขด้วย 2 แต่เราจะนำไปใช้อย่างไร?

ประโยคนี้หมายความว่าอย่างไร:

ดังนั้นเราจึงสามารถตัดสินใจได้ว่าเราจะเลื่อนลงหนึ่งขั้นก่อนเสมอ (หรือขวา)

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