Гурвалжин дахь хамгийн их замын нийлбэр  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Арцезиум CodeNation GE Эрүүл мэндийн PayU Uber Zoho
Динамик програмчлал

Асуудлын мэдэгдэл  

“Гурвалжин дахь хамгийн их замын нийлбэр” гэсэн бодлогод танд хэдэн бүхэл тоо өгөгдсөн болохыг зааж өгсөн. Эдгээр бүхэл тоонуудыг гурвалжин хэлбэрээр байрлуулсан болно. Та гурвалжингийн оройноос эхэлж байгаа бөгөөд доод эгнээнд хүрэх хэрэгтэй. Үүнийг хийхийн тулд та дараагийн эгнээний зэргэлдээ нүд рүү шилжинэ. Тэгэхээр та гурвалжингаас тогтоосон байдлаар доошоо хөдөлж байхдаа хамгийн дээд нийлбэр нь хэд вэ?

Жишээ нь  

Гурвалжин дахь хамгийн их замын нийлбэрPin

  1
 2 3
5 8 1
12

Тайлбар
Та дараахь байдлаар замаар доошоо бууж болно. 1-> 3-> 8 бол энэ зам нь таныг хамгийн ихдээ 12 болоход хүргэнэ.

арга барил  

Тэгэхээр гурвалжин дахь хамгийн их замын нийлбэрийг хэрхэн яаж шийдэх вэ? Өнөөг хүртэл бид эдгээр төрлийн асуудлуудыг сайн мэддэг байсан. Бидэнд ийм төрлийн асуудал тулгарах бүрт. Харгис хэрцгий хүчний арга нь үргэлж хүрэх газраа хүрэх бүх боломжит арга замыг бий болгох явдал юм. Зам бүрийн нийлбэрийг тооцоолж оновчтой үр дүнгийн хариуг үргэлжлүүлэн шинэчлээрэй. Гэхдээ энэ хандлага нь биднээс замыг бий болгохыг шаарддаг тул энэ арга нь маш үр ашиггүй юм. Зам үүсгэх нь цаг хугацааны хувьд нарийн төвөгтэй шинжтэй даалгавар гэдгийг бид сайн мэднэ.

Тиймээс үүнийг шийдэхийн тулд өөр арга замыг бодох хэрэгтэй. Дараа нь динамик програмчлал бидний аврах ажилд ирдэг. Учир нь замыг үүсгэхийн оронд нүднээс доод мөрөнд хүрэх хамгийн дээд хэмжээ юу болохыг бид мэдэж болох байсан. Ингэснээр бид түүнтэй зэргэлдээ байгаа мөрөн дээрх эгнээний үр дүнг авч чадна. Тиймээс бид жижиг дэд асуудлуудыг шийдэхийн тулд АН-ыг ашигладаг. Дараа нь эдгээр дэд асуудлын үр дүнг нэгтгэж, анхны асуудлын хариуг олох болно.

мөн үзнэ үү
Сегмент мод

Нэгдүгээрт, бид сүүлийн эгнээний нүднүүдийн хариуг бөглөнө үү. Доод эгнээний нүднүүдээс эхлэх боломжтой хамгийн дээд нийлбэр нь тухайн тоо юм гэдгийг бид мэднэ. Үүний дараа бид доод эгнээний дээрх эгнээ рүү шилжинэ. Одоогийн эгнээний нүд бүрийн хувьд түүний доор байрлах эгнээний хажууд байгаа нүднүүдийн 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 массивыг үүсгэсэн. Тиймээс орон зайн нарийн төвөгтэй байдал нь бас олон гишүүнт юм.