Знайдіть максимальну довжину зміїної послідовності  


Рівень складності Жорсткий
Часто запитують у Амазонка CodeNation Expedia Яндекс
Динамічне програмування Матриця

У задачі “Знайти максимальну довжину зміїної послідовності” зазначено, що ми отримали 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

Пояснення

Знайдіть максимальну довжину зміїної послідовностіPin

Підхід  

Проблема вимагає знайти зміїну послідовність з максимальною довжиною, і ми отримуємо сітку як вхід. Підхід наївної або грубої сили - це починати з верхнього лівого кута сітки, а використання рекурсії проходить через правого та нижнього сусіда. Подібним чином ці клітини йдуть до своїх сусідів і так далі, поки ви не знайдете клітину такою, що рух вперед не є можливим через встановлені умови. Використовуючи рекурсію, де загалом ми маємо чотири рекурсивні виклики, складність часу буде на вищій стороні.

Дивись також
Перестановка регістру літер

Замість наведеного вище підходу ми можемо піти далі Динамічне програмування оскільки ми описуємо проблему за допомогою рекурсивного рішення. Потім просто запам'ятайте його, щоб оптимізувати рішення. Складність часу для вищезазначеного підходу була експоненціальною, але з використанням динамічне програмування може звести його до полінома. Для цієї проблеми ми розглянемо два стани, спочатку індекс рядка, а потім індекс стовпця. Кожна комірка в таблиці DP буде залежати від своєї трохи вище та лише лівої комірки. Якщо нам також потрібні клітинки, які обираються для відповіді, ми переходимо через таблицю DP і відповідно до результату для кожної комірки. Ми вирішуємо, яка комірка була підібрана для формування послідовності.

код  

Код С ++ для пошуку максимальної довжини зміїної послідовності

#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 - кількість рядків і стовпців відповідно. Складність часу залежить від розміру сітки. Тому що це потрібно для обчислення кількості комірок у сітці. Таким чином, у найгіршому випадку нам потрібно подорожувати цілою сіткою.

Дивись також
Надрукуйте n термінів послідовності Ньюмена-Конвея

Складність простору

O (N * M), оскільки ми створюємо сітку DP того самого розміру, що і сітка введення.