حداکثر مجموع مسیر در یک مثلث


سطح دشواری متوسط
اغلب در ارسیسیوم CodeNation GE بهداشت و درمان PayU حال بارگذاری ZOHO
برنامه نویسی پویا

بیان مسأله

مسئله "حداکثر مجموع مسیر در یک مثلث" بیان می کند که تعدادی عدد صحیح به شما داده می شود. این اعداد صحیح به صورت مثلث مرتب شده اند. شما از بالای مثلث شروع می کنید و باید به ردیف پایین برسید. برای انجام این کار ، به سلولهای مجاور در ردیف بعدی منتقل می شوید. بنابراین وقتی در حال حرکت به سمت مثلث به روش تعریف شده هستید ، حداکثر مبلغی که می توانید بدست آورید چیست؟

مثال

حداکثر مجموع مسیر در یک مثلث

  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

کد جاوا برای یافتن حداکثر مجموع مسیر در یک مثلث

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) را انجام می داد. بنابراین ، پیچیدگی زمان نیز چند جمله ای است.

پیچیدگی فضا

O (N ^ 2) از آنجا که ما یک آرایه 2D DP ایجاد کردیم. بنابراین پیچیدگی فضا نیز چند جمله ای است.