Unique Paths

Q: ما صيغة المسارات الفريدة؟

الإجابة هي معامل ثنائي الحدين C(m+n-2, m-1) . يتضمن كل مسار m-1 حركة إلى الأسفل و n-1 حركة إلى اليمين، بأي ترتيب، ويؤدي اختيار الحركات الهابطة من بين الحركات الـ m+n-2 إلى تحديد المسار. بالنسبة إلى شبكة 3 × 4، فإن C(5, 2) = 10.

متوسطالبرمجة الديناميكية رياضيات ومحاكاة

+10

يبدأ روبوت في الخلية العلوية اليسرى من شبكة تضم m صفوفًا وn أعمدة، وعليه الوصول إلى الخلية السفلية اليمنى. تنقله كل حركة خلية واحدة إلى اليمين أو خلية واحدة إلى الأسفل. أعد عدد المسارات المختلفة التي يمكنه سلوكها.

الدالة

uniquePaths(m: integer, n: integer) → integer

minteger: عدد الصفوف في الشبكة
ninteger: عدد الأعمدة في الشبكة
تُرجعinteger: عدد المسارات المختلفة من الخلية العلوية اليسرى إلى الخلية السفلية اليمنى

القيود

1 ≤ m, n ≤ 100
الإجابة لا تتجاوز 2 × 10⁹، لذا فهي تتسع في عدد صحيح موقّع من 32 بت.

أمثلة

المدخلات: m = 3n = 4
المخرجات: 10
الشرح: يتكوّن كل مسار من حركتين إلى الأسفل و3 حركات إلى اليمين، أي 5 حركات إجمالًا. ويتحدد المسار باختيار الحركتين اللتين تتجهان إلى الأسفل من بين الحركات الخمس، وهناك 10 طرق لاختيارهما.

+14 اختبارات مخفية عند الإرسال

سؤال إضافي

بالنسبة إلى شبكة بحجم 100 × 100، يتكوّن الجواب من 59 رقمًا. كيف ستحسبه بترديده modulo 10^9+7 باستخدام الصيغة، عندما لا تعود القسمة على i تنجح؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

إن سرد المسارات واحدًا تلو الآخر أمر ميؤوس منه: فشبكة 17 × 17 تضم بالفعل 601,080,390 مسارًا. عليك أن تحسبها دون سردها. المسارات إلى خلية ما هي مجموع المسارات إلى الخلية التي فوقها والمسارات إلى الخلية التي على يسارها، وهذا يحوّل الشبكة إلى جدول تملؤه في مرور واحد. والمسار ليس سوى ترتيب من الحركات إلى الأسفل وإلى اليمين، وهذا يتيح صيغة مغلقة.

احسب كل مسار باستخدام الاستدعاء الذاتي

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

فكّر في آخر حركة للروبوت إلى الخلية السفلية اليمنى. إما أن يكون قد وصل إليها نزولًا من الخلية التي فوقها، أو باتجاه اليمين من الخلية التي على يسارها، وليس بالطريقتين معًا. لذا فإن المسارات عبر شبكة m × n هي المسارات عبر الشبكة الأقصر بصف واحد، uniquePaths(m-1, n)، مضافًا إليها المسارات عبر الشبكة الأضيق بعمود واحد، uniquePaths(m, n-1).

يتوقف الاستدعاء الذاتي عند شبكة لها صف واحد أو عمود واحد، حيث لا يستطيع الروبوت إلا أن يتحرك في خط مستقيم، ولذلك يوجد مسار واحد بالضبط. ينتهي كل مسار بإحدى الحركتين، لذا يُحتسب كل مسار مرة واحدة ويكون المجموع صحيحًا.

هذه الطريقة بطيئة لأن كل مسار ينتهي بحالة أساسية تُرجع 1، لذا فإن عدد الاستدعاءات لا يقل عن الإجابة نفسها. تستلزم شبكة بحجم 17 × 17 أكثر من 600 مليون استدعاء، وتصل الاختبارات إلى إجابات تقارب 1.6 × 10^9. تُحسب الشبكات الأصغر نفسها مرات كثيرة: إذ يتم الوصول إلى (m-1, n-1) مرة من كل واحدة من الحالتين الأبويتين، وتتضاعف مرات التكرار كلما تعمقنا.

الخوارزمية

إذا كان m أو n يساوي 1، فأعِد 1: فالمسار الوحيد خط مستقيم.
وإلا، فاحسب المسارات التي تكون حركتها الأخيرة إلى الأسفل، uniquePaths(m-1, n).
احسب المسارات التي تكون حركتها الأخيرة إلى اليمين، uniquePaths(m, n-1).
أعِد مجموعهما.

def uniquePaths(m, n):
    # One row or one column: the only path is a straight line
    if m == 1 or n == 1:
        return 1
    # The last move came down from the row above or right from the column before
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)

املأ الشبكة صفًا تلو الآخر

الفكرة

يسأل الاستدعاء التكراري عن الخلايا نفسها مرارًا وتكرارًا، ولا يوجد سوى m × n خلية. احسب عدد المسارات إلى كل خلية مرة واحدة، بترتيب تكون فيه الخلايا التي تحتاج إليها جاهزة دائمًا.

الحالة: paths[r][c] هو عدد المسارات من الخلية العلوية اليسرى إلى الصف r، والعمود c. علاقة التكرار: paths[r][c] = paths[r-1][c] + paths[r][c-1]، أي المسارات التي تصل من الأعلى، بالإضافة إلى المسارات التي تصل من اليسار. الحالات الأساسية: لكل خلية في الصف العلوي وفي العمود الأيسر مسار واحد، وهو خط مستقيم. الترتيب: صفًا بعد صف، من اليسار إلى اليمين، بحيث تكون الخلية التي فوقها والخلية التي على يسارها قد حُسبتا قبل أن تحتاج إليها.

عندما تكون m = 3 وn = 4، تكون الصفوف 1 1 1 1، ثم 1 2 3 4، ثم 1 3 6 10، والإجابة هي الخلية الأخيرة، 10.

والآن لاحظ ما تقرؤه عملية الملء: الصف الذي فوق الصف الذي تملؤه فقط. لذا احتفظ بصف واحد. قبل أن تحدّث row[c]، تظل تحمل العدد من الصف الذي فوقه، بينما تحمل row[c-1] بالفعل العدد الجديد على يساره، لذا فإن row[c] += row[c-1] هي علاقة التكرار كاملة. يظل الزمن O(m × n)، وتنخفض الذاكرة من O(m × n) إلى O(n).

الخوارزمية

أنشئ row يحتوي على n عناصر، جميعها 1: الصف العلوي.
كرّر m-1 مرة، مرة واحدة لكل صف أسفل الصف العلوي.
في كل صف، من أجل c من 1 إلى n-1، أضف row[c-1] إلى row[c]. تبقى row[0] مساوية لـ 1: فهذا هو العمود الأيسر.
أعِد row[n-1].

def uniquePaths(m, n):
    # row[c] counts the paths into column c of the current row.
    # The top row is all 1s: the only way along it is straight right.
    row = [1] * n
    for _ in range(m - 1):
        for c in range(1, n):
            # Paths from above (the old row[c]) plus paths from the left (the new row[c-1])
            row[c] += row[c - 1]
    return row[n - 1]

عدّ الحركات باستخدام معامل ثنائي الحدين

الفكرة

يتضمن كل مسار بالضبط m-1 حركة إلى الأسفل وn-1 حركة إلى اليمين، أي m+n-2 حركة إجمالًا، بترتيب ما. وكل ترتيب يُعدّ مسارًا صالحًا: فالروبوت لا ينفّذ أبدًا أكثر من m-1 حركة إلى الأسفل أو n-1 حركة إلى اليمين، ولذلك لا يغادر الشبكة أبدًا. لذا فالمسار هو نفسه اختيار أيّ m-1 حركة من أصل m+n-2 حركة تكون إلى الأسفل، والإجابة هي المعامل الثنائي C(m+n-2, m-1).

الجدول في الطريقة السابقة هو مثلث باسكال بعد تدويره إلى جانبه، وهذا هو سبب اتفاق الطريقتين. لحساب المعامل دون استخدام مضروبات ضخمة، ابنِه عاملًا تلو الآخر. مع N = m+n-2 وk = min(m, n)-1، اضرب في N-k+i ثم اقسم على i، حيث تتراوح i من 1 إلى k. بعد الخطوة i، تكون القيمة المتراكمة C(N-k+i, i)، وهي عدد صحيح، لذا فإن كل عملية قسمة تكون دقيقة.

عندما تكون m = 3 وn = 4: تكون N = 5 وk = 2، وتتغير القيمة كالتالي: 1 × 4 / 1 = 4، ثم 4 × 5 / 2 = 10. اختيار الجانب الأقصر يُبقي الحلقة عند 99 خطوة أو أقل. حاصل الضرب قبل القسمة الأخيرة يساوي k مضروبًا في الإجابة. في شبكة 17 × 17، يساوي ذلك 16 × 601,080,390، أي نحو 9.6 × 10^9، وهو أكبر من نطاق 32 بت، لذا خزّنه في عدد صحيح ذي 64 بت.

الخوارزمية

عيّن N = m+n-2، وهو عدد الحركات، وk = min(m, n)-1.
ابدأ عدّادًا بسعة 64 بت بالقيمة 1.
من أجل i من 1 إلى k، اضرب العدّاد في N-k+i، ثم اقسمه على i.
أعِد العدّاد.

def uniquePaths(m, n):
    # A path is m+n-2 moves; count the ways to choose which of them go down.
    # Choose along the shorter side so the loop stays short.
    moves = m + n - 2
    k = min(m, n) - 1
    count = 1
    for i in range(1, k + 1):
        # count goes from C(moves-k+i-1, i-1) to C(moves-k+i, i); the division is exact
        count = count * (moves - k + i) // i
    return count

أخطاء شائعة وحالات حدّية

عملية العد قصيرة، لذا تختبئ الأخطاء عند أطراف الشبكة وفي حجم الأعداد.

حساب (m+n-2)! ثم القسمة على العامليْن الآخرين يتسبب في تجاوز السعة قبل تجاوز الإجابة بوقت طويل: 21! يتجاوز بالفعل نطاق 64 بت، وتصل قيمة m+n-2 إلى 105 في شبكة أبعادها 100 × 7.
القسمة قبل الضرب، كما في count / i * (N-k+i)، تؤدي إلى اقتطاع الناتج، لأن count ليس دائمًا من مضاعفات i. اضرب أولًا: فحاصل الضرب يقبل القسمة دائمًا دون باقٍ.
قد يتجاوز حاصل الضرب count × (N-k+i) القيمة 2^31 حتى عندما لا تتجاوزها الإجابة. خزّنه في عدد صحيح من 64 بت.
إن تركت الصف العلوي أو العمود الأيسر بقيمة 0 بدلًا من 1، فستصبح كل الخلايا 0. للشبكة ذات الصف الواحد أو العمود الواحد مسار واحد بالضبط.
تبديل الصفوف والأعمدة لا يغيّر الإجابة، لأن C(m+n-2, m-1) = C(m+n-2, n-1).

أسئلة شائعة4

ما صيغة المسارات الفريدة؟

الإجابة هي معامل ثنائي الحدين C(m+n-2, m-1). يتضمن كل مسار m-1 حركة إلى الأسفل وn-1 حركة إلى اليمين، بأي ترتيب، ويؤدي اختيار الحركات الهابطة من بين الحركات الـm+n-2 إلى تحديد المسار. بالنسبة إلى شبكة 3 × 4، فإن C(5, 2) = 10.

ما هو التعقيد الزمني لمسألة المسارات الفريدة؟

يستغرق جدول البرمجة الديناميكية زمنًا قدره O(m × n)، ومساحة قدرها O(n) عند الاحتفاظ بصف واحد. تستغرق صيغة ذي الحدين زمنًا قدره O(min(m, n)) ومساحة قدرها O(1). يُجري الاستدعاء التكراري المباشر عددًا من الاستدعاءات لا يقل عن عدد المسارات، وهو عدد أُسّي بالنسبة إلى m + n.

كيف تحل مسألة المسارات الفريدة عندما تكون بعض الخلايا محجوبة؟

استخدم الجدول نفسه، واضبط عدد المسارات في الخلية المحظورة على 0 حتى لا يمر أي مسار عبرها. لم يعد الصف العلوي والعمود الأيسر مكوّنين بالكامل من الرقم 1: فكل خلية تأتي بعد خلية محظورة في الصف العلوي يكون فيها عدد المسارات 0. لم تعد الصيغة صالحة، لأنها تفترض أن كل ترتيب للحركات مسموح به.

لماذا يتطابق جدول المسارات الفريدة مع مثلث باسكال؟

تضيف كل خلية قيمة الخلية التي فوقها والخلية التي على يسارها، وهذه هي القاعدة التي تُنشئ مثلث باسكال عند قراءته على امتداد أقطاره. تحتوي الخلية في الصف r والعمود c على C(r+c, r)، لذا تحتوي الخلية السفلية اليمنى على C(m+n-2, m-1).

Python

def uniquePaths(m, n):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

m = 3
n = 4

المتوقع

Unique Paths

الدالة

القيود

أمثلة

تلميحات

الحل

احسب كل مسار باستخدام الاستدعاء الذاتي

املأ الشبكة صفًا تلو الآخر

عدّ الحركات باستخدام معامل ثنائي الحدين

أخطاء شائعة وحالات حدّية

أسئلة شائعة4

مسائل مشابهة