اشرح البرمجة الديناميكية والأساليب الأخرى بأمثلة

جدول المحتويات

1 المقدمة

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

2. أطول زيادة لاحقة

2.1 وصف المشكلة

تعد مشكلة التتابع الأكبر (LIS) أحد تحديات البرمجة الكلاسيكية التي تتطلب إيجاد طول أطول تتابع لتسلسل معين ، بحيث يتم فرز جميع العناصر اللاحقة بترتيب تصاعدي. التسلسل اللاحق هو تسلسل يمكن اشتقاقه من تسلسل آخر عن طريق حذف بعض العناصر دون تغيير ترتيب العناصر المتبقية.

على سبيل المثال ، ضع في اعتبارك التسلسل [10 ، 9 ، 2 ، 5 ، 3 ، 7 ، 101 ، 18]. أطول زيادة لاحقة هنا هي [2 ، 3 ، 7 ، 101] ، وطولها 4.

2.2 الحل في JavaScript

لحل مشكلة LIS في JavaScript ، يمكننا استخدام البرمجة لتقسيم المشكلة إلى مشكلات فرعية أصغر وحلها بكفاءة. إليك حل خطوة بخطوة مع تعليقات مفصلة لمساعدتك على فهم الكود:

function longestIncreasingSubsequence(nums) {
  const n = nums.length;
  if (n === 0) return 0;
  
  // Initialize an array of length n, filled with 1s, as the minimum length of any LIS is 1
  const dp = Array(n).fill(1);
  
  // Iterate through the elements in the nums array
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      // Check if the current element is greater than the previous one
      if (nums[i] > nums[j]) {
        // If it is, update the dp array with the maximum length found so far
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  
  // Find the maximum length of the LIS by iterating through the dp array
  let maxLIS = dp[0];
  for (let i = 1; i < n; i++) {
    maxLIS = Math.max(maxLIS, dp[i]);
  }
  
  // Return the maximum length of the LIS
  return maxLIS;
}

لفهم هذا الحل ، دعنا نقسم الأجزاء الرئيسية:

نقوم بتهيئة مصفوفة تسمى dp بنفس طول أرقام ، ونملأها بـ 1s. سيقوم هذا الصفيف بتخزين طول LIS المنتهي في كل فهرس.
ثم نستخدم حلقتين متداخلتين للتكرار خلال العناصر في الأعداد .
إذا كان العنصر الحالي أكبر من العنصر السابق ، نقوم بتحديث dp مع الحد الأقصى للطول الموجود حتى الآن.
أخيرًا ، نجد الحد الأقصى لطول LIS عن طريق التكرار خلال dp وإعادته.

تعقيد الوقت وتعقيد المكان هي كما يلي:

تعقيد الوقت: O (ن ^ 2)

التعقيد الزمني للحل هو O (n ^ 2) لأن لدينا حلقتين متداخلتين. تتكرر الحلقة الخارجية فوق العناصر الموجودة في مصفوفة الإدخال وتتكرر الحلقة الداخلية عبر العناصر حتى الفهرس الحالي في الحلقة الخارجية. في أسوأ الحالات ، سيتم تشغيل كلتا الحلقتين n من المرات ، مما ينتج عنه إجمالي عمليات n * n. لذلك ، فإن التعقيد الزمني هو O (n ^ 2).

تعقيد الفضاء: O (n)

تعقيد مساحة الحل هو O (n) لأننا نستخدم مصفوفة إضافية dp لتخزين طول LIS المنتهي عند كل فهرس. حجم dp يساوي طول أرقام مصفوفة الإدخال ، وهو n. بصرف النظر عن dp ، نستخدم بعض المتغيرات ، لكن استهلاكها للمساحة ثابت ولا يعتمد على حجم الإدخال. لذلك ، فإن تعقيد الفضاء هو O (n).

إذا سألت هل هناك حل أفضل وأكثر كفاءة لنفس التحدي؟

نعم ، هناك حل أفضل لتعقيد الوقت لمشكلة التتابع الأطول تزايدًا باستخدام خوارزمية بحث ثنائية. التعقيد الزمني لهذا النهج هو O (n * log (n)).

إليك الكود والشرح للنهج الأفضل:

function longest_increasing_subsequence(nums) {
    let tails = [];
    tails[0] = nums[0];
    let length = 1;

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < tails[0]) {
            tails[0] = nums[i];
        } else if (nums[i] > tails[length - 1]) {
            tails[length++] = nums[i];
        } else {
            tails[lower_bound(tails, 0, length - 1, nums[i])] = nums[i];
        }
    }

    return length;
}

function lower_bound(arr, start, end, key) {
    while (start < end) {
        let mid = Math.floor((start + end) / 2);
        if (arr[mid] < key) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }

    return start;
}

في هذا النهج ، نحافظ على ذيول ، والتي تخزن الحد الأدنى من عناصر الذيل لجميع التكرارات اللاحقة المتزايدة التي رأيناها حتى الآن. صفيف ذيول ، ويمثل طوله طول أطول زيادة لاحقة. نقوم بالتكرار من خلال أرقام ولكل عنصر:

إذا كان العنصر أصغر من العنصر الأول في ذيول ، فإننا نستبدل العنصر الأول بالعنصر الحالي.
إذا كان العنصر أكبر من العنصر الأخير في ذيول ، فإننا نلحق العنصر بنهاية الأطراف ، مما يزيد من طول LIS بمقدار 1.
بخلاف ذلك ، نجد أصغر عنصر في ذيول أكبر من أو يساوي العنصر الحالي باستخدام Lower_bound (بحث ثنائي) ، واستبدل هذا العنصر بالعنصر الحالي.

هذا النهج أسرع لأنه ، لكل عنصر في مصفوفة الإدخال ، نقوم بإجراء عملية بحث ثنائية تستغرق وقت O (log (n)). نظرًا لوجود عناصر n في مصفوفة الإدخال ، فإن التعقيد الزمني الإجمالي هو O (n * log (n)).

يتمثل الاختلاف الأساسي بين حلول O (n ^ 2) و O (n log (n)) في التقنية المستخدمة لتحديث حلول المشكلة الفرعية. يستخدم نهج O (n ^ 2) البرمجة الديناميكية بحلقة متداخلة ، بينما يستخدم نهج O (n log (n)) البحث الثنائي لتحسين التحديثات. يعتبر حل O (n * log (n)) أكثر كفاءة ، خاصة بالنسبة لمصفوفات الإدخال الكبيرة.

3. أطول نتيجة مشتركة

3.1 وصف المشكلة

تعد مشكلة أطول عواقب مشتركة (LCS) مشكلة تقليدية في علوم الكمبيوتر تتضمن إيجاد أطول تتابع مشترك بين تسلسلين معينين. التسلسل اللاحق هو تسلسل يظهر بنفس الترتيب في كلا التسلسلين ولكن ليس بالضرورة على التوالي. على سبيل المثال ، أطول سلسلة متتالية شائعة من السلاسل "ABCD" و "ACDF" هي "ACD".

3.2 الحل في JavaScript

لحل مشكلة التتابع الأكثر شيوعًا ، سنستخدم البرمجة الديناميكية. يتيح لنا هذا النهج تقسيم المشكلة إلى مشكلات فرعية أصغر وحلها مرة واحدة فقط. إليك حل JavaScript:

function longestCommonSubsequence(str1, str2) {
  const m = str1.length;
  const 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];
}

لفهم الكود ، دعنا نقسمه خطوة بخطوة:

نحدد أولاً أطوال كل من سلاسل الإدخال m و n .
نقوم بإنشاء مصفوفة ثنائية الأبعاد dp بأبعاد (m + 1) x (n + 1) وتهيئة جميع العناصر إلى 0.
نقوم بعمل حلقة من خلال كل حرف من كلا السلاسل ، ومقارنتها في كل خطوة.
إذا كانت الأحرف متطابقة ، فإننا نزيد القيمة في dp في الموضع الحالي بإضافة 1 إلى القيمة في الموضع القطري (لأعلى ولليسار). هذا يمثل إضافة الحرف المطابق الحالي إلى LCS الموجود حتى الآن.
إذا لم تتطابق الأحرف ، فسنأخذ القيمة القصوى من الخلية أعلاه أو الخلية الموجودة على اليسار. هذا يمثل النظر في LCS التي تم العثور عليها حتى الآن بدون الأحرف الحالية.
بعد التكرار عبر كلا السلسلتين ، تمثل القيمة الموجودة في الركن الأيمن السفلي من صفيف dp طول أطول سلسلة متتابعة مشتركة.

التعقيد الزمني لهذا الحل هو O (m * n) ، حيث m و n هما أطوال سلاسل الإدخال. هذا لأننا نحتاج إلى المرور عبر كل حرف في كلتا السلسلتين ومقارنتهما.

التعقيد المكاني للحل هو أيضًا O (m * n) بسبب المصفوفة ثنائية الأبعاد dp التي أنشأناها لتخزين النتائج الوسيطة للمشكلات الفرعية.

دعونا نجري بعض التحسين ونقوم بمراجعة الكود.

يحتوي حل البرمجة الديناميكية المقدم أعلاه على تعقيد زمني لـ O (m * n) ، حيث m و n هما أطوال سلاسل الإدخال. في حين أنه قد لا يكون من الممكن تحسين التعقيد الزمني بشكل كبير للحالة العامة ، يمكننا تحسين التعقيد المكاني للحل.

التعقيد الحالي للفضاء هو أيضًا O (m * n) بسبب صفيف ثنائي الأبعاد dp . يمكننا تحسين ذلك باستخدام مصفوفة متدرجة وتتبع الصفوف الحالية والسابقة فقط. هذا يقلل من تعقيد الفضاء إلى O (دقيقة (م ، ن)). إليك حل JavaScript الأمثل:

function longestCommonSubsequence(str1, str2) {
  if (str1.length < str2.length) {
    [str1, str2] = [str2, str1];
  }

  const m = str1.length;
  const 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];
}

في هذا الحل الأمثل ، نقوم أولاً بتبديل str1 و str2 إذا كان طول str1 str2 . هذا يضمن أن str2 هي دائمًا السلسلة الأقصر ، مما يقلل من تعقيد المساحة. بعد ذلك ، بدلاً من تهيئة مصفوفة ثنائية الأبعاد بأبعاد (م + 1) × (ن + 1) ، نقوم بإنشاء صفيف ثنائي الأبعاد بأبعاد 2 × (ن + 1) .

داخل الحلقات ، نقوم بتحديث dp باستخدام عامل التشغيل modulo ( ٪ ) للتبديل بين الصفين. هذا يعني أننا نقوم فقط بتخزين الصف الحالي والصف السابق ، مما يقلل بشكل فعال من تعقيد المساحة إلى O (min (m ، n)).

يرجى ملاحظة أن التعقيد الزمني يظل O (m * n) لأننا ما زلنا بحاجة إلى تكرار كل حرف في كلتا السلسلتين ومقارنتهما. ومع ذلك ، تم تحسين تعقيد المساحة الآن ، مما يجعل الحل أكثر كفاءة من حيث استخدام الذاكرة.

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

4.1 وصف المشكلة

تتضمن مشكلة السلسلة الفرعية الأطول متقاربة العثور على أطول سلسلة فرعية متجاورة لسلسلة معينة تقرأ نفس السلسلة للأمام وللخلف. على سبيل المثال ، بالنظر إلى السلسلة "babad" ، فإن أطول سلسلة فرعية متناظرة هي إما "bab" أو "aba".

4.2 الحل في JavaScript

تتمثل إحدى طرق حل هذه المشكلة في استخدام البرمجة الديناميكية. إليك حل JavaScript:

function longestPalindromicSubstring(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(false));
  let maxLen = 1;
  let start = 0;

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

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;

      if (len === 2) {
        dp[i][j] = s[i] === s[j];
      } else {
        dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1];
      }

      if (dp[i][j] && len > maxLen) {
        maxLen = len;
        start = i;
      }
    }
  }

  return s.substring(start, start + maxLen);
}

في هذا الحل ، نقوم أولاً بإنشاء مصفوفة ثنائية الأبعاد dp ، حيث dp [i] [j] صحيحة إذا كانت السلسلة الفرعية من الفهرس i إلى j متطابقة. نقوم بتهيئة العناصر القطرية لـ dp على أنها صحيحة لأن الأحرف الفردية دائمًا ما تكون متجانسة.

بعد ذلك ، نقوم بالتكرار خلال السلسلة باستخدام حلقتين متداخلتين. تتكرر الحلقة الخارجية عبر الأطوال المحتملة للأوتار الفرعية (من 2 إلى طول سلسلة الإدخال) ، وتتكرر الحلقة الداخلية من خلال مواضع بداية السلاسل الفرعية. إذا كانت السلسلة الفرعية الحالية متناظرة ، فإننا نقوم بتحديث dp وتتبع موضع البداية والحد الأقصى لطول المتماثل.

أخيرًا ، نعيد أطول سلسلة فرعية متناظرة باستخدام السلسلة الفرعية .

تعقيد الوقت: O (n ^ 2) ، حيث n هو طول سلسلة الإدخال. هذا لأننا نحتاج إلى المرور عبر جميع السلاسل الفرعية الممكنة والتحقق مما إذا كانت متناظرة.

تعقيد الفضاء: O (n ^ 2) ، بسبب المصفوفة ثنائية الأبعاد dp التي تخزن المعلومات المتناظرة لجميع السلاسل الفرعية الممكنة.

البرمجة الديناميكية هي مجرد إحدى الطرق لحل مشكلة السلسلة الفرعية الأطول متناظرة ، وقد قدمتها لأنها تقنية مستخدمة على نطاق واسع لمثل هذه المشاكل. ومع ذلك ، هناك طرق أخرى لحل هذه المشكلة ، ويمكنني تقديم حل بديل باستخدام تقنية التوسيع حول المركز.

تعتمد تقنية التوسيع حول المركز على فكرة التكرار خلال السلسلة ، ولكل حرف ، التوسيع للخارج للعثور على أطول سلسلة فرعية متناظرة تتضمن تلك الشخصية. إليك الحل في JavaScript باستخدام هذا الأسلوب:

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

function longestPalindromicSubstring(s) {
  if (s == null || s.length < 1) return '';

  let start = 0;
  let end = 0;

  for (let i = 0; i < s.length; i++) {
    const len1 = expandAroundCenter(s, i, i);
    const len2 = expandAroundCenter(s, i, i + 1);
    const len = Math.max(len1, len2);

    if (len > end - start) {
      start = i - Math.floor((len - 1) / 2);
      end = i + Math.floor(len / 2);
    }
  }

  return s.substring(start, end + 1);
}

في هذا الحل ، نحدد أولاً الدالة المساعدة expandAroundCenter ، والتي تُرجع طول أطول سلسلة فرعية متناظرة تتمحور حول المؤشرات المحددة. بعد ذلك ، نقوم بالتكرار خلال سلسلة الإدخال واستدعاء الوظيفة المساعدة للعثور على أطول سلسلة فرعية متناظرة لكل حرف.

تعقيد الوقت: O (n ^ 2) ، حيث n هو طول سلسلة الإدخال. في أسوأ الحالات ، نحتاج إلى التوسع حول كل حرف في سلسلة الإدخال ، وهو ما يستغرق وقتًا تربيعيًا.

تعقيد الفضاء: O (1) ، لأننا لا نستخدم أي هياكل بيانات إضافية لتخزين النتائج الوسيطة ، ولا يعتمد استخدام الذاكرة على حجم سلسلة الإدخال.

قد يكون لهذا الأسلوب أداء أفضل من البرمجة الديناميكية في بعض الحالات لأنه يمكنه تخطي بعض عمليات التحقق غير الضرورية عند التوسع حول المركز. ومع ذلك ، لا تزال كلتا الطريقتين تتمتعان بتعقيد زمني لـ O (n ^ 2).

إذن ، هل هناك تعقيد زمني أفضل من O (n ^ 2)؟

نعم ، هناك خوارزمية تسمى خوارزمية Manacher التي تحل مشكلة السلسلة الفرعية الأطول متناظرة مع تعقيد زمني أفضل لـ O (n). تم تصميم هذه الخوارزمية خصيصًا للعثور على أطول سلسلة فرعية متناظرة بشكل أكثر كفاءة عن طريق تجنب عمليات التحقق الزائدة واستخدام المعلومات المحسوبة مسبقًا.

إليك تطبيق خوارزمية Manacher في JavaScript:

function manachersAlgorithm(s) {
  if (s == null || s.length === 0) return '';

  let modifiedString = '#';
  for (let i = 0; i < s.length; i++) {
    modifiedString += s[i] + '#';
  }

  const p = new Array(modifiedString.length).fill(0);
  let center = 0;
  let rightBoundary = 0;
  let maxLen = 0;
  let maxLenCenter = 0;

  for (let i = 1; i < modifiedString.length - 1; i++) {
    if (rightBoundary > i) {
      const mirror = 2 * center - i;
      p[i] = Math.min(rightBoundary - i, p[mirror]);
    }

    while (
      i + p[i] + 1 < modifiedString.length &&
      i - p[i] - 1 >= 0 &&
      modifiedString[i + p[i] + 1] === modifiedString[i - p[i] - 1]
    ) {
      p[i]++;
    }

    if (i + p[i] > rightBoundary) {
      center = i;
      rightBoundary = i + p[i];
    }

    if (p[i] > maxLen) {
      maxLen = p[i];
      maxLenCenter = i;
    }
  }

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

في هذه الخوارزمية ، نقوم أولاً بتعديل سلسلة الإدخال عن طريق إضافة أحرف خاصة (على سبيل المثال ، "#") بين الأحرف الأصلية. يساعد هذا في التعامل مع المتناظرات المتساوية والفردية الطول بشكل موحد. بعد ذلك ، نستخدم المصفوفة p لتخزين نصف القطر المتناظر المتمركز في كل حرف من السلسلة المعدلة.

نقوم بالتكرار من خلال السلسلة المعدلة ونقوم بتحديث نصف القطر المتناظر لكل حرف مع الحفاظ على تتبع الحد الأيمن للون المتناظر الحالي ومركزه. نحن نستخدم المعلومات حول نصف القطر المتناظر المحسوب مسبقًا لتخطي بعض عمليات التحقق الزائدة وتجنب العمل الإضافي.

تعقيد الوقت: O (n) ، حيث n هو طول سلسلة الإدخال. تؤدي خوارزمية Manacher عددًا خطيًا من العمليات من خلال تجنب عمليات التحقق الزائدة واستخدام المعلومات المحسوبة مسبقًا.

تعقيد الفضاء: O (n) ، حيث نقوم بتخزين نصف القطر المتناظر لكل حرف من السلسلة المعدلة ، والتي لها طول يتناسب مع طول سلسلة الإدخال.

توفر خوارزمية Manacher حلاً أسرع لأطول مشكلة سلسلة فرعية متقاربة مقارنةً بالبرمجة الديناميكية وطرق التوسيع حول المركز ، والتي لها تعقيد زمني لـ O (n ^ 2).

5. أطول نتيجة متناظرة

5.1 وصف المشكلة

في هذه المسألة ، نحتاج إلى إيجاد أطول تتابع متناظر في سلسلة معينة. على عكس السلسلة الفرعية ، لا تتطلب السلاسل اللاحقة أن تكون الأحرف متجاورة في السلسلة الأصلية ، ولكن يجب أن تحافظ على ترتيبها.

5.2 الحل في JavaScript

يمكننا حل هذه المشكلة باستخدام البرمجة الديناميكية. تكمن الفكرة في إنشاء جدول ثنائي الأبعاد لتخزين أطوال السلاسل الفرعية الأطول متناظرة.

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];
}

في هذا الحل ، نقوم أولاً بتهيئة جدول ثنائي الأبعاد dp بحجم nxn ، حيث n هو طول سلسلة الإدخال. قمنا بتعيين العناصر القطرية لـ dp على 1 نظرًا لأن الحرف الفردي دائمًا ما يكون متماثلًا.

ثم نكرر من خلال الجدول ، ونملأه بأطوال أطول متناظرة لاحقة لجميع السلاسل الفرعية. إذا كانت الأحرف في بداية ونهاية السلسلة الفرعية متطابقة ، فإننا نضيف 2 إلى قيمة السلسلة الفرعية الداخلية. بخلاف ذلك ، نقوم بتعيين القيمة على الحد الأقصى للصف السابق والعمود السابق.

يتم تخزين الإجابة النهائية في الخلية العلوية اليمنى من الجدول ، dp [0] [n - 1] .

تعقيد الوقت: O (n ^ 2) ، حيث n هو طول سلسلة الإدخال. نحتاج إلى ملء الجدول ثنائي الأبعاد بحجم nxn .

تعقيد الفضاء: O (n ^ 2) ، حيث نقوم بتخزين أطوال أطول متناوبات متتالية في جدول dp .

سؤالنا المعتاد: هل هناك وقت أفضل أو تعقيد مكاني أفضل من O (n ^ 2)؟

لا يوجد تعقيد زمني أفضل بكثير من O (n ^ 2) لأطول مشكلة عاقبة متقاربة باستخدام البرمجة الديناميكية. ومع ذلك ، يمكنك تحسين تعقيد المساحة باستخدام صفيف متداول أو صفيفتين 1D بدلاً من صفيف ثنائي الأبعاد.

إليك حل محسّن مع تعقيد مساحة O (n):

function longestPalindromicSubsequence(s) {
  const n = s.length;
  let prev = Array(n).fill(0);
  let curr = Array(n).fill(0);

  for (let i = n - 1; i >= 0; i--) {
    curr[i] = 1;
    for (let j = i + 1; j < n; j++) {
      if (s[i] === s[j]) {
        curr[j] = prev[j - 1] + 2;
      } else {
        curr[j] = Math.max(prev[j], curr[j - 1]);
      }
    }
    [prev, curr] = [curr, prev];
  }

  return prev[n - 1];
}

في هذا الحل ، نستخدم صفيفتين 1D ، prev و current ، لتمثيل الصف السابق والصف الحالي لجدول dp الأبعاد. هذا يقلل من تعقيد الفضاء إلى O (n) مع الحفاظ على نفس التعقيد الزمني لـ O (n ^ 2).

باختصار ، يظل التعقيد الزمني O (n ^ 2) ، ولكن تم تحسين تعقيد الفضاء إلى O (n) باستخدام هذا النهج الأمثل.

6. أقصى منتج Subarray

6.1 وصف المشكلة

تتضمن مشكلة Maximum Product Subarray العثور على مصفوفة فرعية متقاربة ضمن مصفوفة ذات بعد واحد من الأرقام التي تحتوي على أكبر منتج. قد تحتوي مصفوفة الإدخال على أرقام موجبة وسالبة.

6.2 الحل في JavaScript

لحل هذه المشكلة ، يمكننا استخدام البرمجة الديناميكية. نحن نتتبع الحد الأقصى والحد الأدنى من المصفوفات الفرعية للمنتج المنتهية في كل موضع ، حيث قد يكون الرقم الحالي سالبًا ، مما قد يحول الحد الأدنى للمنتج إلى الحد الأقصى للمنتج عند ضربه.

إليك الحل في JavaScript:

function maxProductSubarray(nums) {
  const n = nums.length;
  let maxProd = nums[0];
  let minProd = nums[0];
  let maxSoFar = nums[0];

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

  return maxSoFar;
}

في هذا الحل ، نقوم بالتكرار من خلال أرقام . في كل موضع ، نحسب الحد الأقصى والحد الأدنى من المصفوفات الفرعية للمنتج المنتهية في ذلك الموضع. نقوم بتحديث الحد الأقصى الإجمالي للمنتج عندما نجد منتجًا أكبر.

التعقيد الزمني لهذا الحل هو O (n) لأننا نجعل واحدًا فقط يمر عبر مصفوفة الإدخال. تعقيد الفضاء هو O (1) لأننا نستخدم فقط مساحة إضافية ثابتة لتخزين النتائج الوسيطة.

باختصار ، يحتوي حل JavaScript هذا على تعقيد زمني لـ O (n) وتعقيد مساحة O (1) لمشكلة Maximum Product Subarray.

7. أكبر مستطيل في الرسم البياني

7.1 وصف المشكلة

تتضمن مشكلة أكبر مستطيل في مدرج تكراري العثور على أكبر مساحة مستطيلة يمكن تكوينها داخل مدرج تكراري. يتم تمثيل المدرج التكراري كمصفوفة من الأعداد الصحيحة ، حيث يمثل كل عنصر ارتفاع الشريط وعرض كل شريط هو 1.

7.2 الحل في JavaScript

لحل هذه المشكلة ، يمكننا استخدام بنية بيانات المكدس لتتبع مؤشرات الأشرطة في الرسم البياني. تساعدنا هذه الطريقة في العثور بكفاءة على أكبر مستطيل ممكن لكل شريط.

إليك الحل في JavaScript:

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 > 0 && h < heights[stack[stack.length - 1]]) {
      const height = heights[stack.pop()];
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }

  return maxArea;
}

في هذا الحل ، نكرر ارتفاعات . نحتفظ بمكدس لتتبع مؤشرات القضبان بترتيب غير تنازلي لارتفاعاتها. عندما نجد شريطًا بارتفاع أصغر ، فإننا نخرج العناصر من المكدس ونحسب مساحة المستطيل التي يمكن تشكيلها باستخدام الشريط المنبثق باعتباره الأقصر.

التعقيد الزمني لهذا الحل هو O (n) لأننا ندفع ونفجر كل عنصر من ارتفاعات مرة واحدة على الأكثر. التعقيد المكاني هو O (n) حيث نستخدم مكدس لتخزين مؤشرات الأعمدة.

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

يعتبر الحل المقدم أعلاه ، مع التعقيد الزمني لـ O (n) والتعقيد المكاني لـ O (n) ، هو الحل الأمثل لأكبر مستطيل في مشكلة الرسم البياني. من غير المحتمل أن تجد خوارزمية أكثر فاعلية من حيث الوقت أو تعقيد المكان.

والسبب هو أنه في أسوأ الحالات ، عليك فحص كل شريط في الرسم البياني مرة واحدة على الأقل لتحديد أكبر مساحة مستطيلة. تستلزم هذه الحقيقة تعقيدًا زمنيًا أقل تحديدًا لـ O (n). يستفيد الحل القائم على التكديس أعلاه من ذلك عن طريق الحفاظ على مجموعة من المؤشرات ، مما يضمن معالجة كل شريط مرة واحدة فقط.

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

8.1 وصف المشكلة

مشكلة سقوط البيض هي مشكلة كلاسيكية حيث يتم إعطاؤك بيضة ومبنى من k . تحتاج إلى تحديد أعلى أرضية يمكن أن تسقط منها البيضة دون أن تنكسر. الهدف هو إيجاد الحد الأدنى من عدد المحاولات اللازمة لإيجاد الحل.

8.2 الحل في JavaScript

يمكن حل مشكلة سقوط البيض باستخدام البرمجة الديناميكية. تكمن الفكرة في استخدام مصفوفة ثنائية الأبعاد dp ، حيث dp [i] [j] الحد الأدنى لعدد المحاولات المطلوبة للعثور على أعلى أرضية يمكن أن تسقط منها البيضة دون أن تنكسر ، مع الأخذ في الاعتبار i البيض و j الطوابق.

function eggDrop(n, k) {
  const dp = Array(n + 1)
    .fill()
    .map(() => 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 ^ 2) ، وتعقيد الفضاء هو O (n * k). ومع ذلك ، من الممكن تحسين هذا الحل بشكل أكبر باستخدام البحث الثنائي بدلاً من البحث الخطي عن الحلقة الداخلية. سيؤدي ذلك إلى تقليل التعقيد الزمني إلى O (n * k * log (k)).

بشكل عام ، تعد مشكلة إسقاط البيض مشكلة صعبة يمكن حلها باستخدام البرمجة الديناميكية. من خلال تقسيم المشكلة إلى مشاكل فرعية أصغر وحل كل مشكلة فرعية مرة واحدة فقط ، يمكننا إيجاد الحل الأمثل وتقليل عدد المحاولات اللازمة للعثور على أعلى أرضية يمكن أن تسقط منها البيضة دون أن تنكسر.

9. عد بت

9.1 وصف المشكلة

عدد صحيح غير سالب ، لكل رقم i في النطاق 0 ≤ i ≤ num احسب عدد 1 في تمثيلهم الثنائي وأعدهم كمصفوفة.

9.2 الحل في JavaScript

يمكننا حل هذه المشكلة باستخدام البرمجة الديناميكية. يمكننا البدء بتهيئة مصفوفة طولها num + 1 مع ضبط جميع القيم على صفر. بعد ذلك ، بالنسبة لكل فهرس i من 1 إلى num ، يمكننا تحديث القيمة عند i لتصبح مساوية للقيمة عند i مقسومًا على 2 زائد باقي i مقسومًا على 2. وينجح هذا لأن عدد 1 في التمثيل الثنائي لـ الرقم i يساوي عدد 1 في التمثيل الثنائي لـ i / 2 زائد 1 إذا i فرديًا ، أو 0 إذا i زوجيًا.

إليك كود JavaScript لهذا الحل:

function countBits(num) {
  const dp = new Array(num + 1).fill(0);
  for (let i = 1; i <= num; i++) {
    dp[i] = dp[Math.floor(i / 2)] + (i % 2);
  }
  return dp;
}

التعقيد الزمني لهذا الحل هو O (n) ، حيث n رقم الإدخال الأسطوانات . هذا لأننا نمرّر جميع الأعداد من 1 إلى الأسطوانات . تعقيد الفضاء هو أيضًا O (n) ، لأننا نستخدم مصفوفة بطول عدد + 1 لتخزين عدد 1 لكل رقم.

بشكل عام ، يعد هذا حلًا بسيطًا وفعالًا لمشكلة بتات العد ، ويوضح قوة البرمجة الديناميكية في حل تحديات الخوارزمية.

10. المربعات المثالية

10.1 وصف المشكلة

بإعطاء عدد صحيح موجب n ، أوجد أقل عدد من الأعداد المربعة الكاملة (على سبيل المثال ، 1 ، 4 ، 9 ، 16 ، ...) والتي مجموعها n .

10.2 الحل في JavaScript

لحل هذه المشكلة ، يمكننا استخدام البرمجة الديناميكية. يمكننا إنشاء مصفوفة dp حيث يخزن dp [i] i .

في البداية ، يمكننا ضبط جميع عناصر المصفوفة dp على Infinity باستثناء العنصر الأول ، والذي سيكون 0. هذا لأنه إذا كانت n تساوي 0 ، فلا توجد مربعات كاملة تلخصها ، وإذا كانت n تساوي 1 ، إذن ، فإن أقل عدد من المربعات الكاملة التي مجموعها هو 1.

يمكننا بعد ذلك تكرار جميع الأعداد من 1 إلى n ولكل رقم i ، يمكننا التحقق من جميع المربعات الكاملة التي تقل عن i . يمكننا بعد ذلك تحديث قيمة dp [i] كحد أدنى dp [i] و dp [i - j * j] + 1 ، حيث j * j مربع كامل أصغر من أو يساوي i .

أخيرًا ، يمكننا إرجاع قيمة dp [n] .

إليك كود JavaScript للحل:

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 * sqrt (n)) وتعقيد الفضاء هو O (n).

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

وصف المشكلة

افترض أن لديك mxn . يمكنك التحرك لأسفل أو لليمين في أي وقت. أنت تحاول الوصول إلى الركن الأيمن السفلي من الشبكة. كم عدد المسارات الفريدة الموجودة؟

الحل في JavaScript

يمكننا استخدام البرمجة الديناميكية لحل هذه المشكلة. نبدأ بتهيئة صفيف ثنائي الأبعاد dp بحجم mxn ، حيث dp [i] [j] عدد المسارات الفريدة للوصول إلى الخلية في (i، j) .

يمكننا ملء الصف الأول والعمود الأول من dp بالرقم 1 ، نظرًا لوجود طريقة واحدة فقط للوصول إلى أي خلية في الصف أو العمود الأول. بعد ذلك ، بالنسبة لجميع الخلايا الأخرى ، يكون عدد المسارات الفريدة هو مجموع عدد المسارات الفريدة للوصول إلى الخلية الموجودة أعلى الخلية مباشرةً والخلية الموجودة على اليسار مباشرةً.

أخيرًا ، تمثل قيمة dp [m-1] [n-1] عدد المسارات الفريدة للوصول إلى الركن الأيمن السفلي من الشبكة.

إليك كود JavaScript للحل:

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) ، لأننا نحتاج إلى ملء كل خلية من dp مرة واحدة بالضبط. تعقيد الفضاء هو أيضًا O (m * n) ، لأننا نستخدم مصفوفة ثنائية الأبعاد لتخزين قيم dp .

خاتمة

في الختام ، تعد البرمجة الديناميكية تقنية قوية يمكن أن تساعد في حل المشكلات المعقدة بطريقة أكثر كفاءة من الخوارزميات الأخرى. في هذه المقالة ، استكشفنا العديد من المشكلات الصعبة وقدمنا حلولًا لها في JavaScript باستخدام البرمجة الديناميكية. ناقشنا بيانات المشكلة ، وقدمنا تفسيرات مفصلة للحلول ، وقدمنا أمثلة رمز مع تحليل تعقيد الوقت والمكان.

لقد رأينا كيف يمكن استخدام البرمجة الديناميكية لتحسين الوقت والمساحة المعقدة للخوارزميات ، مما يؤدي إلى حلول أكثر كفاءة. تعلمنا أيضًا أنه يمكن أن يكون هناك المزيد من التحسينات الممكنة بخلاف حلول البرمجة الديناميكية النموذجية ، كما هو موضح في الحلول المحسّنة لبعض المشكلات.

جدول المحتويات

1 المقدمة

2. أطول زيادة لاحقة

2.1 وصف المشكلة

2.2 الحل في JavaScript

3. أطول نتيجة مشتركة

3.1 وصف المشكلة

3.2 الحل في JavaScript

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

4.1 وصف المشكلة

4.2 الحل في JavaScript

5. أطول نتيجة متناظرة

5.1 وصف المشكلة

5.2 الحل في JavaScript

6. أقصى منتج Subarray

6.1 وصف المشكلة

6.2 الحل في JavaScript

7. أكبر مستطيل في الرسم البياني

7.1 وصف المشكلة

7.2 الحل في JavaScript

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

8.1 وصف المشكلة

8.2 الحل في JavaScript

9. عد بت

9.1 وصف المشكلة

9.2 الحل في JavaScript

10. المربعات المثالية

10.1 وصف المشكلة

10.2 الحل في JavaScript

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

وصف المشكلة

الحل في JavaScript

خاتمة

احمد رضوان

نظام إدارة المحتوى بدون رأس: الحل الخالي من الصداع لنظام إدارة المحتوى

أطلق العنان لقوة OAuth: رحلة إلى تطبيقات آمنة وموثوقة

ربما يعجبك أيضا

كيفية حل أول 100 مشكلة لمشروع أويلر 11-15

كيفية حل أول 100 مشكلة لمشروع أويلر 6-10

كيفية حل أول 100 مشكلة لمشروع أويلر 1-5