अधिकतम लम्बाइ सर्प अनुक्रम फेला पार्नुहोस्


कठिनाई तह हार्ड
बारम्बार सोधिन्छ अमेजन CodeNation Expedia Yandex
डायनामिक प्रोग्रामिंग म्याट्रिक्स

समस्या "अधिकतम लम्बाइ सर्प अनुक्रम फेला पार्नुहोस्" भन्छ कि हामीसँग a प्रदान गरिएको छ ग्रिड समावेश गर्दै पूर्णांकहरू। कार्य भनेको अधिकतम लम्बाईको साथ सर्प क्रम खोज्नु हो। १ को निरपेक्ष भिन्नता संग ग्रिड मा आसन्न संख्या भएको एक अनुक्रम, साँप अनुक्रमको रूपमा परिचित छ। एक संख्याको लागि निकट तत्त्वहरू संख्याहरू हुन् जुन यो छोडिन्छ र माथिको छिमेकीहरू, जुन ग्रीड भित्र रहेको छ। सामान्यतया, यदि तपाईं ग्रिडमा (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

स्पष्टीकरण

अधिकतम लम्बाइ सर्प अनुक्रम फेला पार्नुहोस्

दृष्टिकोण

समस्या अधिकतम लम्बाइ संग सर्प क्रम खोज्न सोध्छ र हामी एक इनपुट को रूप मा ग्रिड प्रदान गरीन्छ। एक भोली वा जबरदस्ती दृष्टिकोण दृष्टिकोण ग्रिडको माथि बायाँ कुनाबाट सुरू गर्नु हो, र रिकर्सन प्रयोग गर्दा यसको दायाँ र तल्लो छिमेकी हुँदै जान्छ। त्यस्तै प्रकारका ती कक्षहरू तिनीहरूका छिमेकीहरूमा जान्छन् र जब सम्म तपाईंले यस्तो सेल फेला पार्नुहुन्न जुन सर्त लगाइएको सर्तका कारण अगाडि बढ्ने विकल्प हुँदैन। पुनरावृत्ति प्रयोग गर्दा जहाँ हामीसँग चारवटा रिकर्सिभ कलहरू हुन्छन्, समय जटिलता उच्च तर्फ जाँदैछ।

माथिको दृष्टिकोणको सट्टामा हामी साथ जान सक्दछौं डायनामिक प्रोग्रामिंग किनभने हामी एउटा रिकर्सिभ समाधान प्रयोग गरेर समस्या वर्णन गर्दछौं। त्यसो भए समाधानलाई अनुकूलन गर्न केवल यसलाई मेमोनाइज गर्नुहोस्। माथिको दृष्टिकोणको लागि समय जटिलता घातीय तर प्रयोग गरीरहेको थियो गतिशील प्रोग्रामिंग यसले बहुपदमा कम गर्न सक्छ। यस समस्याको लागि, हामी दुई राज्यहरू हेर्नेछौं, पहिलो प index्क्ति अनुक्रमणिका र त्यसपछि स्तम्भ अनुक्रमणिका। 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

जाभा कोड अधिकतम लम्बाई साँप अनुक्रम फेला पार्न

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 क्रमशः पows्क्ति र स्तम्भहरूको संख्या हो। समय जटिलता ग्रिड को आकार मा निर्भर छ। किनभने यो ग्रिडमा सेलहरूको संख्या गणना गर्न आवश्यक छ। यसैले अत्यन्त नराम्रो परिदृश्यमा, हामीले पूरै ग्रिडको यात्रा गर्नु आवश्यक छ।

ठाउँ जटिलता

O (N * M), किनभने हामी इनपुट ग्रिडको जस्तै आकारको DP ग्रिड सिर्जना गर्दछौं।