Максимална сума на пътя в триъгълник  


Ниво на трудност M
Често задавани в Арцезиум CodeNation GE Healthcare PayU Uber 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

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). По този начин сложността във времето също е многочленна.

Вижте също
Решение за Leetcode на Linindrome Linked List

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

O (N ^ 2) тъй като създадохме 2D DP масив. По този начин космическата сложност също е многочленна.