د مثلث کې د اعظمي لارې برخه


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ارسیم کوډ نیټه په روبل روغتيا پیرو یو über زو
متحرک برنامې

ستونزه بیان

ستونزه "په مثلث کې د اعظمي لارې برخه" وايي چې تاسو ته یو څه انډیور درکول کیږي. دا عددونه د مثلث په ب .ه تنظیم شوي دي. تاسو د مثلث له پورتنۍ برخې څخه پیل کوئ او لاندې قطار ته رسیدو ته اړتیا لرئ. د دې کولو لپاره ، تاسو په راتلونکي قطار کې ځای ته نږدې حجرو ته لاړشئ. نو کله چې تاسو په ټاکل شوي ب inه کې مثلث لاندې حرکت کوئ ، نو اعظمي اندازه څه شی ترلاسه کولی شئ؟

بېلګه

د مثلث کې د اعظمي لارې برخه

  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 ارې رامینځته کړې. پدې توګه د ځای پیچلتیا هم ډیری پولی ده.