أقصى مجموع مسار في المثلث  


مستوى الصعوبة متوسط
كثيرا ما يطلب في Arcesium CodeNation جنرال إلكتريك للرعاية الصحية PayU اوبر زوهو
البرمجة الديناميكية

المشكلة بيان  

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

مثال  

أقصى مجموع مسار في المثلثدبوس

  1
 2 3
5 8 1
12

تفسير
يمكنك ببساطة التحرك على المسار بالطريقة التالية. 1-> 3-> 8 ، سيجعلك هذا المسار تصل إلى الحد الأقصى للمبلغ وهو 12.

الرسالة  

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

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

انظر أيضا
شجرة القطعة

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

كود C ++ للعثور على أقصى مجموع للمسار في مثلث  

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int maximumPathSumInTriangle(vector<vector<int>> &input)
{
    int n = input.size();
    // start from row above bottom row
    // since the bottom row cells are the answers themselves
  for(int i=n-2;i>=0;i--)
  {
      // start from left to right in column
    for(int j=0;j<=i;j++)
    {
      if(input[i+1][j] > input[i+1][j+1])
        input[i][j] += input[i+1][j];
      else
        input[i][j] += input[i+1][j+1];
    }
  }
  return input[0][0];
}

int main()
{
    int n;cin>>n; // number of rows
    vector<vector<int>> input(n, vector<int>(n, 0));
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++)
            cin>>input[i][j];
    }
    cout<<maximumPathSumInTriangle(input);
}

}
3
1
2 3
5 8 1
12

كود Java للعثور على أقصى مجموع للمسار في مثلث  

import java.util.*;

class Main{
  static int maximumPathSumInTriangle(int input[][], int n)
  {
      // start from row above bottom row
      // since the bottom row cells are the answers themselves
    for(int i=n-2;i>=0;i--)
    {
        // start from left to right in column
      for(int j=0;j<=i;j++)
      {
        if(input[i+1][j] > input[i+1][j+1])
          input[i][j] += input[i+1][j];
        else
          input[i][j] += input[i+1][j+1];
      }
    }
    return input[0][0];
  }

  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt(); // number of rows
      int input[][] = new int[n][n];
      for(int i=0;i<n;i++){
          for(int j=0;j<=i;j++)
              input[i][j] = sc.nextInt();
      }
      int answer = maximumPathSumInTriangle(input, n);
      System.out.print(answer);
  }
}
3
1
2 3
5 8 1
12

تحليل التعقيد  

تعقيد الوقت

O (N ^ 2)، حيث انتقلنا عبر كل صف وكل عمود. في هذه العملية ، سافرنا إلى كل خلية. ونظرًا لوجود خلايا O (N ^ 2) في المثلث ، فقد استغرق الانتقال لـ DP عملية O (1) فقط. وبالتالي ، فإن تعقيد الوقت هو أيضًا متعدد الحدود.

انظر أيضا
Palindrome المرتبطة قائمة Leetcode الحل

تعقيد الفضاء

O (N ^ 2) منذ أن أنشأنا مجموعة ثنائية الأبعاد DP. وبالتالي فإن تعقيد الفضاء هو أيضًا متعدد الحدود.