Пронађите максималну дужину секвенце змија


Ниво тешкоће Тежак
Често питани у амазонка ЦодеНатион Екпедиа иандек
Динамичко програмирање матрица

Проблем „Пронађи змијску секвенцу максималне дужине“ наводи да смо добили а решетка који садржи интегерс. Задатак је пронаћи змијски низ максималне дужине. Низ који има суседне бројеве у мрежи са апсолутном разликом од 1, познат је као змијски низ. Суседни елементи броја су бројеви који су лево и изнад суседа, с обзиром да постоје унутар мреже. Формално говорећи, ако стојите у (и, ј) ћелији у мрежи, тада ћелије (и, ј-1), (и-1, ј) стоје уз њу с обзиром да леже унутар мреже.

Пример

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

Објашњење

Пронађите максималну дужину секвенце змија

Приступ

Проблем захтева проналажење змијске секвенце максималне дужине и као улаз добијамо мрежу. Приступ наивне или грубе силе треба започети од горњег левог угла мреже, а коришћење рекурзије пролази кроз десног и доњег суседа. Слично из тих ћелија одлазе код својих суседа и тако редом док не пронађете ћелију која креће напред није опција због наметнутих услова. Користећи рекурзију, где генерално имамо четири рекурзивна позива, временска сложеност биће на вишој страни.

Уместо горе наведеног приступа, можемо ићи са Динамичко програмирање јер проблем описујемо помоћу рекурзивног решења. Затим га једноставно упамтите како бисте оптимизовали решење. Сложеност времена за горњи приступ била је експоненцијална, али употребљива динамичко програмирање може свести на полином. За овај проблем ћемо прво размотрити два стања: индекс редова, а затим индекс ступаца. Свака ћелија у табели ДП зависи од своје мало изнад и само леве ћелије. Ако су нам такође требале ћелије које су одабране за одговор, прелазимо преко ДП табеле и према резултату за сваку ћелију. Одлучујемо која ћелија је узета да формира секвенцу.

код

Ц ++ код за проналажење змијске секвенце максималне дужине

#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

Јава код за проналажење змијске секвенце максималне дужине

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

Анализа сложености

Сложеност времена

НА М), где су Н и М број редова односно колона. Сложеност времена зависи од величине мреже. Зато што је то потребно за израчунавање броја ћелија у мрежи. Према томе, у најгорем случају, од нас се захтева да пређемо целу мрежу.

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

НА М), јер стварамо ДП мрежу исте величине као и мрежа улаза.