تسلّق الدرج وتوليفات العملات
العلاقات التكرارية الكلاسيكية أحادية البعد من الصفر
تسلّق الدرج وتوليفات العملات درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
تعرّف إلى مسألة صعود الدرج
يمكنك صعود درجة واحدة أو درجتين في كل مرة. كم عدد الطرق للوصول إلى الدرجة n؟ إن هذه المسألة الكلاسيكية من 1D DP ليست إلا متتالية فيبوناتشي متخفية.
أوجد العلاقة التكرارية
للوصول إلى الدرجة i، لا بد أنك أتيت من i-1 أو من i-2. لذلك تكون dp[i] = dp[i-1] + dp[i-2]، أي نجمع آخر حركتين محتملتين.
dp[i] = dp[i-1] + dp[i-2]حدّد حالات الأساس
توجد طريقة واحدة للبقاء عند الأرض، وطريقة واحدة للوصول إلى الدرجة 1. تهيّئ هاتان حالتي الأساس الجدول بأكمله.
dp[0], dp[1] = 1, 1املأ الجدول واقرأ الإجابة
كرّر من الأسفل إلى الأعلى، وستحتوي الخلية الأخيرة على العدد. الحل الكامل ليس إلا حلقة ملء جدول صغيرة.
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]اختزلها إلى متغيرين
لا تحتاج إلا إلى آخر قيمتين، لذا تخلّص من المصفوفة. هذه النسخة ذات O(1) مساحة هي المفضلة في المسابقات.
a, b = 1, 1
for _ in range(n):
a, b = b, a+bانتقل إلى توليفات العملات
مع إعطائك قيم العملات، احسب عدد الطرق لتكوين المبلغ A. لن يهم الترتيب هنا، لذا نحسب التوافيق لا المتتاليات.
coins = [1, 2, 5]جدول التوافيق
لتكن dp[x] عدد الطرق لتكوين x. ابدأ بطريقة واحدة لتكوين الصفر: مجموعة العملات الخالية.
dp = [0]*(A+1)
dp[0] = 1اجعل حلقة العملات خارجية
ضع حلقة العملات الخارجية حول حلقة المبالغ. يضمن هذا الترتيب احتساب كل توليفة مرة واحدة بالضبط، من دون احتساب التبديلات.
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]التوافيق مقابل التبديلات
إذا بدّلت ترتيب الحلقتين، فستحسب بدلًا من ذلك طرقًا مرتبة. يكفي تغيير تعشيق الحلقتين لقلب معنى الإجابة.
نسخة أقل عدد من العملات
لإيجاد أقل عدد من العملات، خزّن قيمة صغرى بدلًا من مجموع. ابدأ بالقيمة اللانهاية، ثم أضف 1 إلى أفضل مسألة فرعية.
dp[x] = min(dp[x], dp[x-c] + 1)نمط واحد، صور متعددة
تشترك مسألتا الدرج والعملات في بنية واحدة: تجمع كل حالة أو تحسب القيمة الصغرى اعتمادًا على عدد قليل من الحالات السابقة. إذا لاحظت ذلك، فستكتب الشيفرة تلقائيًا.
تحقق سريع
عند حساب توليفات العملات، أي ترتيب للحلقات يتجنب التكرارات؟
مراجعة: اجمع الحركات الأخيرة
يمكنك الآن حل مسألتي الدرج وعدّ العملات باستخدام علاقة تكرارية أحادية البعد. تجمع كل إجابة عددًا قليلًا من الحالات السابقة، ويحدد ترتيب الحلقات الفرق بين التوافيق والتبديلات.
الأسئلة الشائعة
هل درس «تسلّق الدرج وتوليفات العملات» مجاني؟
نعم — نص درس «تسلّق الدرج وتوليفات العملات» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «تسلّق الدرج وتوليفات العملات»؟
العلاقات التكرارية الكلاسيكية أحادية البعد من الصفر تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «تسلّق الدرج وتوليفات العملات»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- المذكرة مقابل الجدولة
- تعريف الحالة والانتقال
- تسلّق الدرج وتوليفات العملات
- أطول تتابع متزايد