تعريف الحالة والانتقال
تسمية معنى dp[i] بدقة
تعريف الحالة والانتقال درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
جوهر البرمجة الديناميكية
تبدأ كل برمجة ديناميكية بتحديد حالة: ماذا تمثل dp[i] فعلًا؟ إذا صغت هذه الجملة بشكل صحيح، اتضح ما تبقى.
يجب أن تكون الحالة دقيقة
اكتب المعنى بالكلمات: dp[i] = الإجابة لأول i عنصرًا. ويؤدي تعريف الحالة الغامض إلى علاقة تكرارية مليئة بالأخطاء.
dp[i] = best total using items 0..i-1الانتقال
يوضح الانتقال كيفية بناء dp[i] من الحالات السابقة. وهو معادلة العلاقة التكرارية في صميم الحل.
dp[i] = dp[i-1] + dp[i-2]الحالات الأساسية تثبّت الحل
إن الحالات الأساسية هي أصغر الحالات التي تعرفها مباشرة. ومن دون نقاط ارتكاز صحيحة، تنحرف كل قيمة لاحقة عن الصواب.
dp[0] = 1اختر ترتيب التقييم
يجب ملء كل حالة بعد الحالات التي تعتمد عليها. وتحدد قاعدة الاعتماد هذه اتجاه حلقاتك.
for i in range(1, n+1): ...أين توجد الإجابة
حدّد الخلية التي تحتوي على النتيجة النهائية. غالبًا ما تكون dp[n]، لكنها أحيانًا تكون القيمة العظمى في الجدول بأكمله.
answer = dp[n] # or max(dp)عدّ الحالات
يحدد عدد الحالات المختلفة ميزانية الزمن لديك. وتحتاج برمجة dp أحادية البعد على n من العناصر إلى ملء O(n) من الحالات.
التكلفة لكل انتقال
يساوي الزمن الإجمالي عدد الحالات مضروبًا في العمل لكل انتقال. ويؤدي انتقال بتعقيد O(n) داخل n من الحالات إلى O(n تربيع).
أضف بُعدًا عند الحاجة
إذا لم يتمكن فهرس واحد من تمثيل الوضع، فأضف فهرسًا آخر. يحوّل البعد الثاني dp[i] إلى dp[i][j].
dp = [[0]*(c+1) for _ in range(n+1)]استعادة الاختيار
لاستعادة الحل الفعلي، خزّن أي انتقال فاز في كل حالة، ثم ارجع من الإجابة إلى الخلف.
choice[i] = "take"قائمة تحقق قابلة لإعادة الاستخدام
الحالة، والانتقال، وحالة الأساس، والترتيب، والإجابة. حدّد هذه العناصر الخمسة بدقة، وستتضح تقريبًا أي علاقة تكرارية في DP.
تحقق سريع
أنت تصمّم خوارزمية DP. ماذا تمثّل dp[i]؟
مراجعة: سمِّ الحالة ثم حلّها
يمكنك الآن تعريف حالة، وكتابة انتقالها، وتعيين حالات الأساس، وتحديد موضع الإجابة. يحوّل هذا المخطط DP من التخمين إلى وصفة واضحة.
الأسئلة الشائعة
هل درس «تعريف الحالة والانتقال» مجاني؟
نعم — نص درس «تعريف الحالة والانتقال» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «تعريف الحالة والانتقال»؟
تسمية معنى dp[i] بدقة تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «تعريف الحالة والانتقال»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- المذكرة مقابل الجدولة
- تعريف الحالة والانتقال
- تسلّق الدرج وتوليفات العملات
- أطول تتابع متزايد