Знайсці максімальную даўжыню змеі паслядоўнасці


Узровень складанасці Жорсткі
Часта пытаюцца ў амазонка CodeNation Expedia Яндэкс
Дынамічнае праграмаванне матрыца

У задачы "Знайсці максімальную даўжыню змяінай паслядоўнасці" гаворыцца, што мы забяспечаны сетка які змяшчае цэлыя. Задача - знайсці змяіную паслядоўнасць з максімальнай даўжынёй. Паслядоўнасць, якая мае суседнія нумары ў сетцы з абсалютнай розніцай 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

Тлумачэнне

Знайсці максімальную даўжыню змеі паслядоўнасці

Падыход

Праблема просіць знайсці змяіную паслядоўнасць з максімальнай даўжынёй, і ў якасці ўваходу мы атрымліваем сетку. Падыходжанне наіўнай або грубай сілы - гэта пачаць з левага верхняга кута сеткі, а выкарыстанне рэкурсіі праходзіць праз яе правага і ніжняга суседа. Аналагічна з гэтых клетак ідуць да сваіх суседзяў і гэтак далей, пакуль вы не знойдзеце ячэйку, такая, што рухацца наперад не магчыма з-за ўсталяваных умоў. Выкарыстоўваючы рэкурсію, дзе ў цэлым у нас чатыры рэкурсіўныя выклікі, складанасць часу будзе на вышэйшым баку.

Замест вышэйапісанага падыходу мы можам пайсці далей Дынамічнае праграмаванне таму што мы апісваем задачу з выкарыстаннем рэкурсіўнага рашэння. Затым проста запомніце яго, каб аптымізаваць рашэнне. Складанасць часу для вышэйзгаданага падыходу была экспанентнай, але з выкарыстаннем дынамічнае праграмаванне можа звесці яго да мнагачлена. Для гэтай праблемы мы разгледзім два стану: спачатку індэкс радка, а потым індэкс слупка. Кожная ячэйка ў табліцы DP будзе залежаць ад яе крыху вышэй і левай ячэйкі. Калі нам таксама спатрэбіліся ячэйкі, якія выбіраюцца для адказу, мы пераходзім па табліцы DP і ў адпаведнасці з вынікам для кожнай ячэйкі. Мы вырашаем, якая клетка была падабрана для фарміравання паслядоўнасці.

код

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), таму што мы ствараем сетку DP таго ж памеру, што і ўваходная сетка.