في هذا المقال، سنغوص في عالم البرمجة الديناميكية (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)

هذا الحل المحسّن هو المعيار في عام 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);
}

خوارزمية ماناتشر (O(n)، مساحة O(n))

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

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. 🚀