Climbing Stairs
تقف عند أسفل درج مكوّن من n درجات. في كل حركة تصعد إما درجة واحدة أو درجتين. يُعدّ مساران مختلفين إذا اختلف تسلسل الحركات، لذا فإن 1, 2 و2, 1 طريقتان مختلفتان. تستقبل دالتك n وتُرجع عدد الطرق المختلفة للوصول إلى القمة.
الدالة
- ninteger
- عدد الدرجات في السُّلَّم
- تُرجعinteger
- عدد المتتاليات المختلفة من خطوات بمقدار 1 وخطوات بمقدار 2 التي تصل إلى الخطوة n
القيود
1 ≤ n ≤ 45- الإجابة تقع ضمن نطاق عدد صحيح موقّع من 32 بت:
n = 45يعطي1836311903.
أمثلة
- المدخلات
- n = 3
- المخرجات
- 3
- الشرح
- يمكن صعود ثلاث درجات على النحو
1, 1, 1، أو1, 2، أو2, 1، لذا توجد 3 طرق.
- المدخلات
- n = 5
- المخرجات
- 8
- الشرح
- كل صعود إلى الخطوة 5 ينتهي بخطوة واحدة من الخطوة 4 (5 طرق للوصول إليها) أو بخطوتين من الخطوة 3 (3 طرق)، لذا فالإجابة هي
5 + 3 = 8.
سؤال إضافي
ماذا لو كانت بعض الخطوات معطّلة، وربما لا تستطيع الوقوف عليها أبدًا؟ كيف تتغيّر علاقة العودية، وما العدد الخاص بالخطوة المعطّلة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
انظر إلى الحركة الأخيرة في أي تسلّق للوصول إلى الدرجة
n. أين كان من الممكن أن تكون واقفًا قبلها مباشرة؟كل صعود إلى الدرجة
nينتهي بخطوة واحدة من الدرجةn-1أو بخطوتين من الدرجةn-2، وليس بكليهما أبدًا. لذا فإن عدد الطرق للوصول إلىnيساوي عدد الطرق للوصول إلىn-1زائد عدد الطرق للوصول إلىn-2.ابدأ من عدد الطرق لصعود درجة واحدة (طريقة واحدة) ودرجتين (طريقتان)، ثم واصل تصاعديًا. لا تحتاج إلا إلى العددين الأخيرين، وكل عدد جديد هو مجموعهما.
الحل
إن تعداد كل طرق الصعود لا يجدي: فهناك 1836311903 طريقة لصعود درج مكوّن من 45 درجة. مفتاح الحل هو الخطوة الأخيرة. كل صعود إلى الدرجة n يمر بالدرجة n-1 أو الدرجة n-2 قبل النهاية مباشرةً، وهذا يعطينا ways(n) = ways(n-1) + ways(n-2)، وهي علاقة فيبوناتشي التراجعية. احسبها تصاعديًا من الأساس، ولن تحتاج إلا إلى متغيرين.
الاستدعاء الذاتي البسيط في الحركة الأخيرة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
قسّم طرق الصعود إلى الدرجة n بحسب خطوتها الأخيرة. يصل مسار صعود ينتهي بخطوة من درجة واحدة إلى الدرجة n-1 قبلها، وهناك ways(n-1) من هذه المسارات. أما مسار الصعود الذي ينتهي بخطوة من درجتين، فيصل إلى الدرجة n-2، وهناك ways(n-2) من هذه المسارات. ينتهي كل مسار صعود بإحدى الطريقتين، ولا ينتهي بأي منهما معًا، لذا ways(n) = ways(n-1) + ways(n-2).
تحتاج الاستدعاءات التكرارية إلى حالتين أساسيتين. لصعود درجة واحدة طريقة واحدة، ولصعود درجتين طريقتان (1, 1 و2). في كلتا الحالتين، تساوي الإجابة n، لذا تعيد الدالة n عندما يكون n ≤ 2، وإلا فتعيد المجموع.
الإجابة صحيحة، لكن عدد العمليات يتضخم بشكل هائل. يطلب climbStairs(5) حساب الدرجة 3 مرتين والدرجة 2 ثلاث مرات، أي 9 استدعاءات إجمالًا، وينمو عدد الاستدعاءات على نحو يشبه نمو الإجابات نفسها. عندما تكون n = 45، تجري الدالة 2269806339 استدعاءً، أي نحو 2.3 × 10^9، وهو عدد أكبر بكثير مما يسمح به حدّ الوقت. لا يتجاوز عمق الاستدعاءات التكرارية n مستويات، لذا تستخدم المكدسة مساحة O(n).
الخوارزمية
- إذا كان
n ≤ 2، فأعِدn. - احسب عدد مرات الوصول إلى الدرجة
n-1باستدعاء递归. - احسب عدد مرات الوصول إلى الدرجة
n-2باستدعاء递归 ثانٍ. - أعِد مجموع العددين.
def climbStairs(n):
if n <= 2:
return n # 1 step: one way, 2 steps: two ways
return climbStairs(n - 1) + climbStairs(n - 2)الاستدعاء الذاتي مع مذكرة
الفكرة
يكون الاستدعاء الذاتي بطيئًا فقط لأنه ينسى. يعتمد كل عدد على k وحده، لذا ما إن تعرف العدد للخطوة k حتى لا يتغير أبدًا. احتفظ بذاكرة مؤقتة، وهي مصفوفة تحتوي على خانة لكل خطوة، واكتب فيها كل عدد في المرة الأولى التي تحسبه فيها. وكل طلب لاحق للخطوة نفسها يقرأ الخانة بدلًا من تكرار الاستدعاء الذاتي.
الآن يُحسب كل عدد من الخطوة 3 إلى الخطوة n مرة واحدة، بعملية جمع واحدة. عندما تكون n = 5، تصل الاستدعاءات إلى الخطوة 2 مرة واحدة، ثم تعود الإجابات إلى الأعلى لتكون 3 و5 و8، ويكون الطلب الثاني للخطوة 3 بحثًا في الذاكرة المؤقتة. وهذا يعني زمنًا قدره O(n) بدلًا من مليارات الاستدعاءات.
تحتوي الذاكرة المؤقتة على n + 1 عددًا، وما زال الاستدعاء الذاتي يبلغ عمقًا قدره n مستوى، لذا تكون المساحة O(n). تعني القيمة 0 في الخانة أن العدد غير معروف بعد، وهذا آمن لأن كل عدد فعلي لا يقل عن 1.
الخوارزمية
- أنشئ مذكرة تحتوي على
n + 1خانة، جميعها 0. - في الدالة المساعدة العودية، أعد
kعندما يكونk ≤ 2. - إذا كانت خانة المذكرة المقابلة لـ
kتساوي 0، فاملأها بنتيجتي الدالة المساعدة لـk-1وk-2بعد جمعهما. - أعد قيمة خانة المذكرة.
- استدعِ الدالة المساعدة باستخدام
n.
def climbStairs(n):
memo = [0] * (n + 1) # memo[k] = ways to reach step k, 0 = not known yet
def ways(k):
if k <= 2:
return k
if memo[k] == 0:
memo[k] = ways(k - 1) + ways(k - 2)
return memo[k]
return ways(n)من الأسفل إلى الأعلى باستخدام متغيرين
الفكرة
اعكس اتجاه الاستدعاء التكراري. بدلًا من البدء من الأعلى وطرح السؤال نزولًا، ابدأ من الأسفل وابنِ الحل صعودًا. عندما تحسب العدد للخطوة k، يكون العددان للخطوتين k-1 وk-2 معروفين بالفعل، ولا تعود بحاجة إلى قراءة أي قيم أقدم. لذا يستبدل متغيران جدول التخزين المؤقت بأكمله.
اجعل prev يحمل العدد للخطوة k-2، وcurr العدد للخطوة k-1. ابدأ بـ prev = 1 وcurr = 2، وهما العددان للخطوتين 1 و2. في كل خطوة، اجمعهما في next، ثم حرّك الزوج إلى الأمام. عندما تكون n = 5، ينتقل الزوج من (1, 2) إلى (2, 3)، ثم (3, 5)، ثم (5, 8)، وتكون curr = 8 هي الإجابة.
تتكرر الحلقة n-2 مرة، مع عملية جمع واحدة في كل مرة، بزمن O(n)، وتحتفظ بثلاثة أعداد صحيحة، بمساحة O(1). احسب next قبل أن تستبدل قيمة prev، وإلا فسيستخدم المجموع قيمة خاطئة.
الخوارزمية
- إذا كان
n ≤ 2، فأعِدn. - عيّن
prev = 1وcurr = 2. - لكل
kمن 3 إلىn، احسبnext = prev + curr، ثم عيّنprev = currوcurr = next. - أعِد
curr.
def climbStairs(n):
if n <= 2:
return n
prev, curr = 1, 2 # ways to reach steps 1 and 2
for _ in range(n - 2):
prev, curr = curr, prev + curr
return curr
أخطاء شائعة وحالات حدّية
العلاقة التكرارية قصيرة، لذا تتمركز معظم الأخطاء في الحالات الأساسية، وزمن التنفيذ، وحدود الأعداد ذات 32 بت.
- تسليم حل الاستدعاء التكراري المباشر. يجتاز الاختبارات الصغيرة، ثم يحتاج إلى نحو
2.3 × 10^9استدعاء عندما تكونn = 45. خزّن كل عدد مرة واحدة. - حالات أساسية خاطئة. للخطوتين طريقتان للصعود:
1, 1و2. إرجاع 1 عندما تكونn = 2يزيح كل إجابة لاحقة: ستحصل على 2 عندما تكونn = 3بدلًا من 3. - عدّ الخيارات بدلًا من تسلسلات الخطوات.
1, 2و2, 1طريقتان للصعود. إذا عددت فقط عدد خطوات 2 التي تخطوها، فستحصل علىn/2 + 1، أي 3 عندما تكونn = 5بدلًا من 8. - ملء جدول من دون التحقق من الحدود. عندما تكون
n = 1، لا يتسع جدول حجمهn + 1 = 2خانات لعدد الخطوة 2. أعدnفورًا عندما تكونn ≤ 2. - التقدم خطوة واحدة أكثر من اللازم. عدد طرق صعود 45 خطوة، 1836311903، يتسع في 32 بت، لكن عدد طرق صعود 46 خطوة هو 2971215073 ولا يتسع. حلقة تحسب قيمة إضافية واحدة ستفيض، وتنتج عددًا سالبًا في Java أو C أو C#.
أسئلة شائعة3
لماذا تُعدّ مسألة صعود الدرج مسألة فيبوناتشي؟
كل صعود إلى الدرجة n ينتهي بخطوة واحدة من n-1 أو بخطوتين من n-2، لذا ways(n) = ways(n-1) + ways(n-2). هذه هي قاعدة فيبوناتشي. مع ways(1) = 1 وways(2) = 2 تكون الأعداد 1، 2، 3، 5، 8، 13، وهي متتالية فيبوناتشي مزاحة بمقدار موضع واحد: ways(n) = F(n+1).
ما هو التعقيد الزمني لمسألة تسلّق الدرج؟
تنفّذ حلقة التصاعد من الأسفل n-2 عملية جمع، لذا تعمل بزمن O(n) وبمساحة إضافية O(1). أما الاستدعاء الذاتي المباشر فزمنه أُسّي: يزداد عدد الاستدعاءات بعامل يقارب 1.618 في كل خطوة، ويصل إلى 2269806339، أي نحو 2.3 × 10^9، عند n = 45. وتُخفّض المذكرة الاستدعاء الذاتي إلى زمن O(n) ومساحة O(n).
ما الفرق بين الحفظ المؤقت والحل من الأسفل إلى الأعلى؟
تُبقي تقنية التخزين المؤقت الدالةَ الاستدعائيةَ الذاتيّة وتخزّن كل نتيجة مؤقتًا في المرة الأولى التي تُحسب فيها، لذا تعمل من الأعلى إلى الأسفل وتحتاج إلى مكدس الاستدعاءات وجدول. تحسب الحلقة من الأسفل إلى الأعلى الأعداد بترتيب تصاعدي، لذا تكون كل قيمة تحتاج إليها معروفةً مسبقًا، ولا تتضمن أي استدعاء ذاتي. تنفّذ كلتاهما عملًا بمقدار O(n). وتتيح لك الحلقة أيضًا الاستغناء عن الجدول والاحتفاظ برقمين.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def climbStairs(n):
# اكتب الكود هنااختبار #1
اختبار #2
وسيط
n = 3
الإخراج المتوقع
3