Максимални збир путање у троуглу  


Ниво тешкоће Средњи
Често питани у Арцесиум ЦодеНатион ГЕ Хеалтхцаре ПаиУ Убер Зохо
Динамичко програмирање

Изјава о проблему  

Проблем „Максимални збир путање у троуглу“ наводи да су вам дати неки цели бројеви. Ови цели бројеви су поређани у облику троугла. Крећете од врха троугла и требате доћи до доњег реда. Да бисте то урадили, преместите се на суседне ћелије у следећем реду. Дакле, када се крећете низ троугао на дефинисан начин, који је максималан збир који можете постићи?

Пример  

Максимални збир путање у троуглу

  1
 2 3
5 8 1
12

Објашњење
Можете се једноставно кретати стазом на следећи начин. 1-> 3-> 8, овај пут ће вас довести до максималне суме која је 12.

Приступ  

Па како да решимо максимални збир путање у троуглу? До сада смо прилично добро упознати са овом врстом проблема. Кад год су нам дате такве врсте проблема. Приступ грубе силе увек је прво створити све могуће начине како доћи до одредишта. А затим наставите да ажурирате одговор за оптималан резултат израчунавањем збира за сваку путању. Али овај приступ је крајње неефикасан јер овај приступ захтева да генеришемо путеве. И ми знамо да је генерисање пута задатак који има експоненцијалну временску сложеност што није добро.

Да бисмо то решили, морамо смислити други приступ. Онда динамичко програмирање долази у наш спас. Јер уместо да генеришемо путање, кад бисмо некако могли знати да је који је максимум који се од ћелије може постићи да би се дошло до доњег реда. На тај начин можемо добити резултат за ћелију која је поред ње, али у реду изнад ње. Дакле, користимо ДП за решавање мањих потпроблема. Затим, комбинујући резултате за те подпроблеме, проналазимо одговоре на изворни проблем.

Види такође
Сегментно дрво

Прво попуњавамо одговор за ћелије у последњем реду. Знамо да је максималан збир који можемо постићи ако кренемо од ћелија у доњем реду сам број. После тога прелазимо на ред изнад доњег реда. За сваку ћелију у тренутном реду можемо одабрати ДП вредности ћелија које су јој суседне у реду одмах испод ње. На овај начин настављамо да идемо према горе. Кад смо стигли до горњег реда, готови смо са проблемом.

Ц ++ код за проналажење максималне суме путање у троуглу  

#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

Анализа сложености  

Сложеност времена

О (Н ^ 2), док смо се кретали по сваком реду и свакој колони. У том процесу путовали смо до сваке ћелије. А пошто је у троуглу било О (Н ^ 2) ћелија и прелаз за ДП је трајао само О (1) операција. Дакле, временска сложеност је такође полиномна.

Види такође
Решење са повезницом са Палиндромом

Сложеност простора

О (Н ^ 2) пошто смо креирали 2Д ДП низ. Стога је сложеност простора такође полином.