പരമാവധി നീളം പാമ്പിന്റെ ക്രമം കണ്ടെത്തുക  


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ആമസോൺ കോഡ്നേഷൻ ബൈ യാൻഡക്സ്
ഡൈനാമിക് പ്രോഗ്രാമിംഗ് മാട്രിക്സ്

“പരമാവധി ദൈർ‌ഘ്യം കണ്ടെത്തുക ഗ്രിഡ് അടങ്ങിയ പൂർണ്ണസംഖ്യകൾ. പരമാവധി നീളമുള്ള ഒരു പാമ്പിന്റെ ക്രമം കണ്ടെത്തുക എന്നതാണ് ചുമതല. ഗ്രിഡിൽ‌ 1 എന്ന കേവല വ്യത്യാസമുള്ള തൊട്ടടുത്ത സംഖ്യകളുള്ള ഒരു ശ്രേണിയെ സ്‌നേക്ക്‌ സീക്വൻസ് എന്ന് വിളിക്കുന്നു. ഒരു നമ്പറിനോട് ചേർന്നുള്ള ഘടകങ്ങൾ ഗ്രിഡിനുള്ളിൽ നിലനിൽക്കുന്നതിനാൽ അവ ഇടത് വശത്തും മുകളിലുമുള്ള അക്കങ്ങളാണ്. Ially പചാരികമായി പറഞ്ഞാൽ, നിങ്ങൾ ഗ്രിഡിലെ (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

വിശദീകരണം

പരമാവധി നീളം പാമ്പിന്റെ ക്രമം കണ്ടെത്തുകമൊട്ടുസൂചി

സമീപനം  

പരമാവധി ദൈർ‌ഘ്യമുള്ള പാമ്പുകളുടെ ക്രമം കണ്ടെത്താൻ പ്രശ്നം ആവശ്യപ്പെടുന്നു, മാത്രമല്ല ഇൻ‌പുട്ടായി ഞങ്ങൾക്ക് ഒരു ഗ്രിഡ് നൽ‌കി. ഗ്രിഡിന്റെ മുകളിൽ ഇടത് കോണിൽ നിന്ന് ആരംഭിക്കുക എന്നതാണ് നിഷ്കളങ്കമായ അല്ലെങ്കിൽ ബ്രൂട്ട് ഫോഴ്‌സ് സമീപനം, ആവർത്തനം ഉപയോഗിക്കുന്നത് അതിന്റെ വലത്, താഴെയുള്ള അയൽവാസികളിലൂടെ കടന്നുപോകുന്നു. അതുപോലെ തന്നെ ആ സെല്ലുകളിൽ നിന്ന് അവരുടെ അയൽവാസികളിലേക്ക് പോകുക, അങ്ങനെ നിങ്ങൾ ഒരു സെൽ കണ്ടെത്തുന്നതുവരെ മുന്നോട്ട് നീങ്ങുന്നത് ഒരു വ്യവസ്ഥയല്ല കാരണം മുന്നോട്ട് പോകുന്നത് ഒരു ഓപ്ഷനല്ല. ഞങ്ങൾ‌ക്ക് നാല് ആവർത്തന കോളുകൾ‌ ഉള്ളിടത്ത് ആവർത്തനം ഉപയോഗിച്ച്, സമയ സങ്കീർ‌ണ്ണത ഉയർന്ന ഭാഗത്തായിരിക്കും.

ഇതും കാണുക
ലെറ്റർ കേസ് ക്രമീകരണം

മുകളിലുള്ള സമീപനത്തിനുപകരം, നമുക്ക് പോകാം ഡൈനാമിക് പ്രോഗ്രാമിംഗ് കാരണം ഒരു ആവർത്തന പരിഹാരം ഉപയോഗിച്ച് ഞങ്ങൾ പ്രശ്നം വിവരിക്കുന്നു. പരിഹാരം ഒപ്റ്റിമൈസ് ചെയ്യുന്നതിന് ഇത് ഓർമ്മിക്കുക. മുകളിലുള്ള സമീപനത്തിനുള്ള സമയ സങ്കീർണ്ണത എക്‌സ്‌പോണൻഷ്യൽ ആയിരുന്നു, പക്ഷേ ഉപയോഗിച്ചിരുന്നു ഡൈനാമിക് പ്രോഗ്രാമിംഗ് ഇത് പോളിനോമിയലായി കുറയ്ക്കാൻ കഴിയും. ഈ പ്രശ്നത്തിനായി, ഞങ്ങൾ ആദ്യം രണ്ട് സംസ്ഥാനങ്ങളെ നോക്കും വരി സൂചികയും തുടർന്ന് നിര സൂചികയും. ഡിപി പട്ടികയിലെ ഓരോ സെല്ലും അതിന്റെ മുകളിലും ഇടത് സെല്ലിലും ആശ്രയിച്ചിരിക്കും. ഉത്തരത്തിനായി തിരഞ്ഞെടുക്കുന്ന സെല്ലുകളും ഞങ്ങൾക്ക് ആവശ്യമുണ്ടെങ്കിൽ, ഞങ്ങൾ ഡിപി പട്ടികയിലൂടെ സഞ്ചരിക്കുകയും ഓരോ സെല്ലിന്റെയും ഫലമനുസരിച്ച് സഞ്ചരിക്കുകയും ചെയ്യുന്നു. സീക്വൻസ് രൂപീകരിക്കുന്നതിന് ഏത് സെൽ തിരഞ്ഞെടുത്തുവെന്ന് ഞങ്ങൾ തീരുമാനിക്കുന്നു.

കോഡ്  

പരമാവധി നീളം കണ്ടെത്താനുള്ള സി ++ കോഡ്

#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

സങ്കീർണ്ണത വിശകലനം  

സമയ സങ്കീർണ്ണത

O (N * M), ഇവിടെ N, M എന്നിവ യഥാക്രമം വരികളുടെയും നിരകളുടെയും എണ്ണമാണ്. സമയ സങ്കീർണ്ണത ഗ്രിഡിന്റെ വലുപ്പത്തെ ആശ്രയിച്ചിരിക്കുന്നു. ഗ്രിഡിലെ സെല്ലുകളുടെ എണ്ണം കണക്കാക്കാൻ അത് ആവശ്യമാണ്. അതിനാൽ ഏറ്റവും മോശം അവസ്ഥയിൽ, ഞങ്ങൾ മുഴുവൻ ഗ്രിഡിലും സഞ്ചരിക്കേണ്ടതുണ്ട്.

ഇതും കാണുക
ന്യൂമാൻ-കോൺവേ സീക്വൻസിന്റെ n നിബന്ധനകൾ അച്ചടിക്കുക

ബഹിരാകാശ സങ്കീർണ്ണത

O (N * M), കാരണം ഇൻപുട്ട് ഗ്രിഡിന് സമാനമായ വലുപ്പത്തിലുള്ള ഡിപി ഗ്രിഡ് ഞങ്ങൾ സൃഷ്ടിക്കുന്നു.