Могойн хамгийн их уртыг олох


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Амазоны CodeNation Expedia Yandex
Динамик програмчлал матриц

"Хамгийн их урттай могойн дарааллыг олох" гэсэн асуудал нь бидэнд a сүлжээ агуулсан байна бүхэл тоо. Даалгавар бол хамгийн их урттай могойн дарааллыг олох явдал юм. Сүлжээнд 1-ийн үнэмлэхүй зөрүүтэй зэргэлдээ тоонуудтай дарааллыг Могойн дараалал гэж нэрлэдэг. Тооны зэргэлдээ элементүүд нь сүлжээнд байрладаг тул хөршүүдийн зүүн ба түүнээс дээш тоонууд юм. Албан ёсоор хэлэхэд, хэрэв та сүлжээний (i, j) нүдэн дээр зогсож байгаа бол (i, j-1), (i-1, j) нүднүүд сүлжээнд хэвтэж байгаа тул зэргэлдээ байна.

Жишээ нь

3 3// dimensions of grid
1 2 3
2 4 5
1 2 1
Maximum length of the Snake Sequence is: 5
The maximum length snake sequence is: 1 2 1 2 1

Тайлбар

Могойн хамгийн их уртыг олох

арга барил

Асуудал нь хамгийн их урттай могойн дарааллыг олохыг хүсч байгаа бөгөөд оролтын хувьд бид сүлжээг өгсөн болно. Гэнэн эсвэл харгис хүчээр хандах хандлага нь сүлжээний зүүн дээд булангаас эхлэх бөгөөд рекурсийг ашиглах нь баруун ба доод хөршөөр дамжин өнгөрдөг. Үүнтэй адилаар эдгээр эсүүд хөршүүд рүүгээ очдог бөгөөд ийм нөхцлийг харгалзан урагшлах нь тийм ч боломжгүй зүйл юм. Ерөнхийдөө бид дөрвөн рекурсив дуудлага хийдэг рекурсийг ашигласнаар цаг хугацааны нарийн төвөгтэй байдал дээд талдаа байх болно.

Дээрх хандлагын оронд бид хамт явж болно Динамик програмчлал Учир нь бид рекурсив шийдлийг ашиглан асуудлыг тодорхойлдог. Дараа нь шийдлийг оновчтой болгохын тулд үүнийг цээжлэх хэрэгтэй. Дээрх хандлагын цаг хугацааны нарийн төвөгтэй байдал нь экспоненциал боловч ашигласан болно динамик програмчлал үүнийг олон гишүүнт болгон бууруулж болно. Энэ асуудлын хувьд бид хоёр төлөвийг эхлээд мөрийн индекс, дараа нь баганын индексийг авч үзэх болно. АН-ын хүснэгтийн нүд бүр нь түүний дээгүүр болон зүүн нүднээс хамааралтай байх болно. Хэрэв хариултанд сонгосон нүднүүд бидэнд хэрэгтэй байсан бол бид АН-ын хүснэгтээр дамжуулж нүд тус бүрийн үр дүнгийн дагуу гарна. Дарааллыг бүрдүүлэхийн тулд аль нүдийг авсныг бид шийднэ.

код

Хамгийн их урттай могойн дарааллыг олох C ++ код

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n=3, m=3;
  int grid[n][m] =
  {
    {1, 2, 3},
    {2, 4, 5},
    {1, 2, 1}
  };

  int dp[n][m];
  int mx = 0, en_i = -1, en_j = -1;
  for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dp[i][j] = 1;
            if(i>0 && abs(grid[i-1][j]-grid[i][j]) == 1)
                dp[i][j] = max(dp[i-1][j]+1, dp[i][j]);
            if(j>0 && abs(grid[i][j-1]-grid[i][j]) == 1)
                dp[i][j] = max(dp[i][j-1]+1, dp[i][j]);
            if(dp[i][j] > mx){
                mx = dp[i][j];
                en_i = i;
                en_j = j;
            }
        }
  }
  cout<<"Maximum length of the Snake Sequence is: "<<mx<<endl;
  cout<<"The maximum length snake sequence is: ";
  int l_i = -1, l_j = -1;
  while(en_i != l_i || en_j != l_j){
        cout<<grid[en_i][en_j]<<" ";
        l_i = en_i, l_j = en_j;
        if(en_i > 0 && dp[en_i][en_j] == dp[en_i-1][en_j] + 1)
            en_i--;
        else if(en_j > 0 && dp[en_i][en_j] == dp[en_i][en_j-1] + 1)
            en_j--;
  }
}
Maximum length of the Snake Sequence is: 5
The maximum length snake sequence is: 1 2 1 2 1

Хамгийн их урттай могойн дарааллыг олох Java код

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int n=3, m=3;
    int grid[][] =
    {
      {1, 2, 3},
      {2, 4, 5},
      {1, 2, 1}
    };

    int dp[][] = new int[n][m];
    int mx = 0, en_i = -1, en_j = -1;
    for(int i=0;i<n;i++){
          for(int j=0;j<m;j++){
              dp[i][j] = 1;
              if(i>0 && Math.abs(grid[i-1][j]-grid[i][j]) == 1)
                  dp[i][j] = Math.max(dp[i-1][j]+1, dp[i][j]);
              if(j>0 && Math.abs(grid[i][j-1]-grid[i][j]) == 1)
                  dp[i][j] = Math.max(dp[i][j-1]+1, dp[i][j]);
              if(dp[i][j] > mx){
                  mx = dp[i][j];
                  en_i = i;
                  en_j = j;
              }
          }
    }
    System.out.println("Maximum length of the Snake Sequence is: "+mx);
    System.out.print("The maximum length snake sequence is: ");
    int l_i = -1, l_j = -1;
    while(en_i != l_i || en_j != l_j){
          System.out.print(grid[en_i][en_j]+" ");
          l_i = en_i; l_j = en_j;
          if(en_i > 0 && dp[en_i][en_j] == dp[en_i-1][en_j] + 1)
              en_i--;
          else if(en_j > 0 && dp[en_i][en_j] == dp[en_i][en_j-1] + 1)
              en_j--;
    }
  	}
}
Maximum length of the Snake Sequence is: 5
The maximum length snake sequence is: 1 2 1 2 1

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N * M), энд N ба M нь мөр ба баганын тоо тус тус байна. Цаг хугацааны нарийн төвөгтэй байдал нь сүлжээний хэмжээнээс хамаарна. Энэ нь сүлжээнд байгаа нүдний тоог тооцоолоход шаардлагатай байдаг. Тиймээс хамгийн муу хувилбараар бид бүхэл бүтэн сүлжээгээр аялах шаардлагатай болдог.

Сансрын нарийн төвөгтэй байдал

O (N * M), Учир нь бид оролтын сүлжээтэй ижил хэмжээтэй АН сүлжээг үүсгэдэг.