Үч бурчтуктагы эң чоң сумма  


Кыйынчылык деңгээли орто
Көп суралган Арцезий CodeNation GE Саламаттыкты сактоо PayU Uber Zoho
Динамикалык программалоо

Маселени билдирүү  

"Үч бурчтуктагы жолдун максималдуу суммасы" маселеси сизге бүтүндөй сандар берилгенин билдирет. Бул сандар үч бурчтук түрүндө жайгаштырылган. Сиз үч бурчтуктун башынан баштап, төмөнкү катарга жетишиңиз керек. Бул үчүн, кийинки катардагы жанаша жайгашкан уячаларга өтөсүз. Ошентип, үч бурчтукту ылдый жылдырганда, эң жогорку сумма канчага жетиши мүмкүн?

мисал  

Үч бурчтуктагы эң чоң сумма

  1
 2 3
5 8 1
12

түшүндүрүү
Жөн гана төмөнкүдөй жол менен ылдый жылса болот. 1-> 3-> 8, бул жол максималдуу суммага жеткенде, 12ге жетет.

жакындоо  

Ошентип, үч бурчтуктагы Maximum path суммасын кантип чечебиз? Ушул кезге чейин биз ушул сыяктуу көйгөйлөрдү жакшы билебиз. Качан гана бизге ушул сыяктуу көйгөйлөр берилет. Катаал күчтөрдүн ыкмасы ар дайым биринчи кезекте көздөгөн жериңизге жетүү үчүн бардык ыкмаларды иштеп чыгуу болуп саналат. Андан кийин ар бир жол үчүн сумманы эсептеп, оптималдуу натыйжага жоопту жаңырта бериңиз. Бирок бул ыкма өтө натыйжасыз, анткени бул ыкма бизден жолдорду түзүүнү талап кылат. Жолдорду жаратуу - бул убакыттын ченемдик татаалдыгы жакшы эмес тапшырма экендигин жакшы билебиз.

Демек, муну чечүү үчүн дагы бир ыкманы ойлонушубуз керек. Андан кийин динамикалык программалоо биздин жардамга келет. Себеби жолдорду жаратуунун ордуна, кандайдыр бир жол менен клеткадан эң төмөнкү сапка жетүүгө боло турган максимум эмне экендигин билсек болмок. Ошентип, жанындагы, бирок анын жогору жагындагы катардагы уяча үчүн натыйжаны алабыз. Ошентип, биз чакан субпроблемаларды чечүү үчүн DP колдонобуз. Андан кийин ошол субпроблемалардын натыйжаларын бириктирип, баштапкы көйгөйгө жооп табабыз.

ошондой эле
Segment Tree

Алгач, акыркы катардагы уячалардын жообун толтурабыз. Төмөнкү катардагы уячалардан баштасак, эң жогорку сумма сандын өзү экендигин билебиз. Андан кийин, биз ылдыйкы катардын жогору жагындагы катарга өтөбүз. Учурдагы катардын ар бир уячасы үчүн, анын астындагы катарда ага жанаша жайгашкан уячалардын 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 чечими

Космостун татаалдыгы

O (N ^ 2) анткени биз 2D DP массивин түздүк. Ошентип, мейкиндиктин татаалдыгы да көп мүчөлүү.