Үшбұрыштағы максималды жол қосындысы


Күрделілік дәрежесі орта
Жиі кіреді Арцезий CodeNation GE Healthcare 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) операциясын алды. Сонымен, уақыттың күрделілігі де көпмүшелікке ие болады.

Ғарыштың күрделілігі

O (N ^ 2) өйткені біз 2D DP массивін құрдық. Сонымен кеңістіктің күрделілігі де көпмүшелікке ие болады.