أقل مجموع لمسار مع العوائق
تمرير أفضل تكلفة عبر الخلايا
أقل مجموع لمسار مع العوائق درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
من العدّ إلى حساب التكلفة
أصبحت كل خلية الآن تحتوي على قيمة، وتريد أرخص مسار إلى الزاوية. ينتقل الهدف من عدّ المسارات إلى تقليل التكلفة.
حدّد الحالة
لتكن dp[i][j] أقل تكلفة إجمالية للوصول إلى الخلية (i, j). الشبكة والحركات نفسهما، لكننا نتتبع المجاميع بدلًا من الأعداد.
الانتقال
اختر الجارَين القادمين الأقل تكلفة، ثم أضف قيمة الخلية الحالية. اختيار min هذا هو جوهر العلاقة التكرارية.
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])حدّد العوائق
العائق هو خلية لا يمكنك الوقوف عليها. امنحها تكلفة لا نهائية حتى لا يكون أي مسار يمر عبرها هو المسار الأدنى.
INF = float('inf')احجبها بطريقة واضحة
عندما تحدد الشبكة أن خلية ما محجوبة، اضبط قيمة dp لها على ما لا نهاية وانتقل إلى الخلية التالية. ستتجنبها خطوة min تلقائيًا.
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 هناك عدم وجود مسار. 🧱
الأسئلة الشائعة
هل درس «أقل مجموع لمسار مع العوائق» مجاني؟
نعم — نص درس «أقل مجموع لمسار مع العوائق» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «أقل مجموع لمسار مع العوائق»؟
تمرير أفضل تكلفة عبر الخلايا تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «أقل مجموع لمسار مع العوائق»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- عدّ المسارات على شبكة
- أقل مجموع لمسار مع العوائق
- أطول تتابع مشترك
- مسافة التحرير خطوةً بخطوة