عدّ المسارات على شبكة

تبدأ من الزاوية العلوية اليسرى لشبكة وتريد الوصول إلى الزاوية السفلية اليمنى. تتحرك في كل خطوة إلى اليمين أو إلى الأسفل. كم عدد المسارات المختلفة الموجودة؟

يمكن الوصول إلى كل خلية من الخلية التي فوقها أو الخلية الموجودة إلى يسارها. هذا التداخل هو بالضبط سبب كون هذه المسألة مسألة DP.

لتكن dp[i][j] عدد الطرق للوصول إلى الخلية (i, j) من نقطة البداية. تسمية الحالة بوضوح تمثّل نصف الحل.

لا تصل إلى الخلية إلا من الأعلى أو من اليسار، لذلك يكون العدد هو مجموعهما. هذا هو الانتقال الذي يحرّك الجدول بأكمله.

للخلية الابتدائية طريقة واحدة فقط للوصول إليها: ألا تفعل شيئًا. لذلك تكون قيمة dp[0][0] مساوية لـ 1 قبل ملء أي شيء آخر.

للخلايا الموجودة في الصف العلوي أو العمود الأيسر مسار مستقيم واحد. يكون العدد فيها دائمًا 1، لأن أحد الجارين يقع خارج الشبكة.

أنشئ جدولًا بحجم m by n واملأه بالأصفار. يضمن تحديد حجمه مسبقًا بقاء الفهارس واضحة وتجنّب المفاجآت.

كرّر على الصفوف ثم الأعمدة، من الأعلى إلى الأسفل ومن اليسار إلى اليمين. يضمن هذا الترتيب جاهزية كلا الجارين قبل استخدامهما.

بعد إكمال الملء، يوجد عدد المسارات في الخلية الأخيرة. تكون الإجابة هي dp[m-1][n-1]، أي الزاوية السفلية اليمنى.

يحتاج كل صف إلى الصف الذي يسبقه فقط، لذا يمكنك الاحتفاظ بـصف واحد وتحديثه في مكانه. وبذلك تنخفض الذاكرة إلى O(n).

عند عدم وجود عوائق، تكون الإجابة معاملًا ثنائيًا: اختر الخطوات التي ستتجه إلى الأسفل من إجمالي الخطوات. تظل DP الخيار الأفضل عند ظهور العوائق.

أنت تملأ dp[i][j] لخلية داخلية مفتوحة. ما الصيغة الصحيحة؟

عرّف dp على أنه عدد المسارات إلى خلية، واضبط dp[0][0] على 1، ثم أضف قيمة الخلية التي فوقها إلى قيمة الخلية التي على يسارها. تحتوي الزاوية على الإجابة. 🧭