في هذه المقالة، سنغوص في عالم البرمجة الديناميكية (DP) وتقنيات التحسين ذات الصلة، مع التركيز على حل بعض التحديات البرمجية خطوة بخطوة.
سنقوم بتحليل كل مشكلة، وعرض حلول متعددة في JavaScript، وشرح تعقيدات الزمن والمساحة.

تظل هذه المشكلات أسئلة مقابلات عالية القيمة في 2025، وتظهر بشكل شائع على منصات مثل LeetCode و HackerRank وتقييمات البرمجة.

---

2. أطول متتالية متزايدة (LIS)

وصف المشكلة

أوجد طول أطول متتالية فرعية من تسلسل معين، بحيث تكون جميع العناصر مرتبة بترتيب متزايد.

مثال: [10, 9, 2, 5, 3, 7, 101, 18] → LIS هو [2, 3, 7, 101]، الطول = 4.

حل DP O(n²) (كلاسيكي)

function longestIncreasingSubsequence(nums) {
  const n = nums.length;
  if (n === 0) return 0;
  const dp = Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

• تعقيد الزمن: O(n²)
• تعقيد المساحة: O(n)

حل مُحسّن O(n log n) (بحث ثنائي)

function longestIncreasingSubsequence(nums) {
  const tails = [];
  for (let num of nums) {
    let l = 0, r = tails.length;
    while (l < r) {
      const mid = Math.floor((l + r) / 2);
      if (tails[mid] < num) l = mid + 1;
      else r = mid;
    }
    tails[l] = num;
  }
  return tails.length;
}

• التعقيد الزمني: O(n log n)
• التعقيد المكاني: O(n)

هذا الحل المُحسَّن هو المعيار لـ LIS في عام 2025.

---

3. أطول تسلسل مشترك (LCS)

وصف المشكلة

أوجد أطول تسلسل مشترك بين سلسلتين.

مثال: "ABCD" و "ACDF" → LCS هو "ACD".

O(m × n) حل البرمجة الديناميكية

function longestCommonSubsequence(str1, str2) {
  const m = str1.length, n = str2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = 1 + dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}

• التعقيد الزمني: O(m × n)
• التعقيد المكاني: O(m × n)

النسخة المُحسَّنة للمساحة O(min(m, n))

function longestCommonSubsequence(str1, str2) {
  if (str1.length < str2.length) [str1, str2] = [str2, str1];
  const m = str1.length, n = str2.length;
  const dp = Array.from({ length: 2 }, () => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i % 2][j] = 1 + dp[(i - 1) % 2][j - 1];
      } else {
        dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j], dp[i % 2][j - 1]);
      }
    }
  }
  return dp[m % 2][n];
}

• تعقيد الزمن: O(m × n)
• تعقيد المساحة: O(min(m, n))

---

4. أطول سلسلة فرعية متناظرة

وصف المشكلة

أوجد أطول سلسلة فرعية متصلة متناظرة.

مثال: "babad" → "bab" أو "aba".

التوسع حول المركز (O(n²), O(1) مساحة)

function expandAroundCenter(s, left, right) {
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    left--;
    right++;
  }
  return right - left - 1;
}

function longestPalindromicSubstring(s) {
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    const len = Math.max(
      expandAroundCenter(s, i, i),
      expandAroundCenter(s, i, i + 1)
    );
    if (len > end - start) {
      start = i - Math.floor((len - 1) / 2);
      end = i + Math.floor(len / 2);
    }
  }
  return s.substring(start, end + 1);
}

Manacher’s Algorithm (O(n), O(n) space)

الحل الأمثل للمقابلات.

function manachersAlgorithm(s) {
  let T = "#" + s.split("").join("#") + "#";
  const P = Array(T.length).fill(0);
  let C = 0, R = 0, maxLen = 0, centerIndex = 0;

  for (let i = 1; i < T.length - 1; i++) {
    if (i < R) P[i] = Math.min(R - i, P[2 * C - i]);
    while (T[i + P[i] + 1] === T[i - P[i] - 1]) P[i]++;
    if (i + P[i] > R) [C, R] = [i, i + P[i]];
    if (P[i] > maxLen) [maxLen, centerIndex] = [P[i], i];
  }

  const start = Math.floor((centerIndex - maxLen) / 2);
  return s.substring(start, start + maxLen);
}

---

5. أطول متتالية متماثلة

وصف المشكلة

أوجد أطول متتالية (ليس مقطعًا) تكون متماثلة.

O(n²) حل البرمجة الديناميكية

function longestPalindromicSubsequence(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(0));

  for (let i = 0; i < n; i++) dp[i][i] = 1;

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2;
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[0][n - 1];
}

• التعقيد الزمني: O(n²)
• التعقيد المكاني: O(n²), قابل للتخفيض إلى O(n) باستخدام المصفوفات المتداولة.

---

6. المصفوفة الفرعية ذات أكبر حاصل ضرب

وصف المشكلة

أوجد المصفوفة الفرعية المتتالية ذات أكبر حاصل ضرب.

حل O(n), O(1)

function maxProductSubarray(nums) {
  let maxProd = nums[0], minProd = nums[0], result = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const curr = nums[i];
    const temp = maxProd;
    maxProd = Math.max(curr, curr * maxProd, curr * minProd);
    minProd = Math.min(curr, curr * temp, curr * minProd);
    result = Math.max(result, maxProd);
  }

  return result;
}

---

7. أكبر مساحة مستطيل في هيستوجرام

وصف المشكلة

أوجد أكبر مساحة مستطيل في هيستوجرام.

حل قائم على المكدس O(n)

function largestRectangleArea(heights) {
  const stack = [];
  let maxArea = 0;

  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    while (stack.length && h < heights[stack.at(-1)]) {
      const height = heights[stack.pop()];
      const width = stack.length === 0 ? i : i - stack.at(-1) - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }

  return maxArea;
}

• التعقيد الزمني: O(n)
• التعقيد المكاني: O(n)

هذا لا يزال الحل الأمثل لعام 2025.

---

8. مشكلة إسقاط البيض

وصف المشكلة

معطى n بيض و k طوابق، ابحث عن الحد الأدنى من المحاولات المطلوبة للعثور على أعلى طابق يمكن إسقاط بيضة منه دون أن تنكسر.

حل البرمجة الديناميكية

function eggDrop(n, k) {
  const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    dp[i][1] = 1;
    dp[i][0] = 0;
  }
  for (let j = 1; j <= k; j++) dp[1][j] = j;

  for (let i = 2; i <= n; i++) {
    for (let j = 2; j <= k; j++) {
      dp[i][j] = Infinity;
      for (let x = 1; x <= j; x++) {
        const res = 1 + Math.max(dp[i - 1][x - 1], dp[i][j - x]);
        dp[i][j] = Math.min(dp[i][j], res);
      }
    }
  }
  return dp[n][k];
}

• تعقيد الوقت: O(n × k²) → يمكن تحسينه إلى O(n × k log k).
• ما زال سؤالًا كلاسيكيًا صعبًا في المقابلات لعام 2025.

---

9. عد البتات

وصف المشكلة

بالنظر إلى العدد num، أعد مصفوفة تحتوي على عدد 1 في التمثيل الثنائي لكل عدد ≤ num.

حل O(n)

function countBits(num) {
  const dp = new Array(num + 1).fill(0);
  for (let i = 1; i <= num; i++) {
    dp[i] = dp[i >> 1] + (i & 1);
  }
  return dp;
}

• التعقيد الزمني: O(n)
• التعقيد المكاني: O(n)

---

10. المربعات الكاملة

وصف المشكلة

أوجد أقل عدد من الأعداد المربعة الكاملة التي مجموعها n.

حل البرمجة الديناميكية

function numSquares(n) {
  const dp = Array(n + 1).fill(Infinity);
  dp[0] = 0;

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j * j <= i; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }
  return dp[n];
}

• التعقيد الزمني: O(n√n)
• التعقيد المكاني: O(n)

---

11. المسارات الفريدة

وصف المشكلة

أوجد عدد المسارات الفريدة في شبكة m × n، مع التحرك فقط لأسفل أو يمين.

حل البرمجة الديناميكية

function uniquePaths(m, n) {
  const dp = Array(m).fill().map(() => Array(n).fill(1));
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
}

• التعقيد الزمني: O(m × n)
• التعقيد المكاني: O(m × n)

---

الخاتمة

البرمجة الديناميكية والتقنيات ذات الصلة (البحث الثنائي، التحسينات المبنية على المكدس، التخزين المؤقت) هي مهارات أساسية للمقابلات في عام 2025. 🚀