خوارزميةاحترافي
البرمجة الديناميكية: مسارات الشبكة
احسب عدد المسارات عبر شبكة تتحرّك فقط إلى اليمين أو إلى الأسفل.
- الزمن
- O(n·m)
- الذاكرة
- O(n·m)
تتبّعها خطوة بخطوة
الخطوة 1 من 8
1function uniquePaths(m, n) {2 const dp = Array.from({ length: m }, () => new Array(n).fill(1));3 for (let r = 1; r < m; r++) {4 for (let c = 1; c < n; c++) {5 dp[r][c] = dp[r - 1][c] + dp[r][c - 1];6 }7 }8 return dp[m - 1][n - 1];9}| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | |||
| 2 | 1 |
ننشئ جدولاً بحجم 3 × 4. لكل خلية في الصف الأول والعمود الأول مسار واحد بالضبط.
درس احترافي
افتح الشرح الكامل
هذا الدرس جزء من الخطة الاحترافية، التي تفتح كل خطوة في كل درس، إضافة إلى تدريبات الأنماط وتقارير الإتقان.
اطّلع على الأسعاركيف تعمل
لا يمكنك دخول خلية إلا من الخلية التي فوقها أو الخلية التي على يسارها. إذن عدد المسارات إلى خلية هو عدد المسارات إلى الخلية التي فوقها زائد عدد المسارات إلى الخلية التي على يسارها. لكل خلية في الصف الأول والعمود الأول مسار واحد بالضبط. املأ الجدول صفاً صفاً، وستحمل الخلية في الزاوية السفلية اليمنى الإجابة. تُحسب كل خلية مرة واحدة: الزمن والذاكرة O(n·m).
تدرّب على اكتشاف هذا النمط →