خوارزميةاحترافي
البرمجة الديناميكية: صعود الدرج
احسب عدد طرق صعود درج بخطوة أو خطوتين في كل مرة، بالبناء على إجابات أصغر.
- الزمن
- O(n)
- الذاكرة
- O(n)
تتبّعها خطوة بخطوة
الخطوة 1 من 8
1function climbStairs(n) {2 const dp = new Array(n + 1).fill(0);3 dp[0] = 1;4 dp[1] = 1;5 for (let i = 2; i <= n; i++) {6 dp[i] = dp[i - 1] + dp[i - 2];7 }8 return dp[n];9}- n
- = 6
- 00
- 01
- 02
- 03
- 04
- 05
- 06
ننشئ مصفوفة dp، حيث سيحفظ dp[i] عدد طرق الوصول إلى الدرجة i.
درس احترافي
افتح الشرح الكامل
هذا الدرس جزء من الخطة الاحترافية، التي تفتح كل خطوة في كل درس، إضافة إلى تدريبات الأنماط وتقارير الإتقان.
اطّلع على الأسعاركيف تعمل
لتصل إلى الدرجة i، جاءت حركتك الأخيرة من الدرجة i − 1 أو الدرجة i − 2. إذن عدد طرق الوصول إلى i هو عدد طرق الوصول إلى i − 1 زائد عدد طرق الوصول إلى i − 2. بدلاً من إعادة حسابها بالعَوْدية، احفظ كل إجابة في مصفوفة واملأها من الأسفل إلى الأعلى. تُحسب كل قيمة مرة واحدة: الزمن O(n) والذاكرة O(n). إنها عَوْدية فيبوناتشي من دون العمل المكرّر.
تدرّب على اكتشاف هذا النمط →