ค้นหาลำดับงูที่มีความยาวสูงสุด  


ระดับความยาก ยาก
ถามบ่อยใน อเมซอน CodeNation Expedia Yandex
การเขียนโปรแกรมแบบไดนามิก มดลูก

ปัญหา "ค้นหาลำดับความยาวสูงสุดของงู" ระบุว่าเราได้รับไฟล์ ตะแกรง ที่มี จำนวนเต็ม. ภารกิจคือการค้นหาลำดับงูที่มีความยาวสูงสุด ลำดับที่มีตัวเลขติดกันในตารางที่มีผลต่างสัมบูรณ์เป็น 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 คือจำนวนแถวและคอลัมน์ตามลำดับ ความซับซ้อนของเวลาขึ้นอยู่กับขนาดของเส้นตาราง เนื่องจากเป็นสิ่งจำเป็นสำหรับการคำนวณจำนวนเซลล์ในตาราง ดังนั้นในสถานการณ์ที่เลวร้ายที่สุดเราจำเป็นต้องเดินทางทั้งกริด

ดูสิ่งนี้ด้วย
พิมพ์ n เงื่อนไขของลำดับนิวแมน - คอนเวย์

ความซับซ้อนของอวกาศ

O (N * M), เนื่องจากเราสร้างกริด DP ที่มีขนาดเท่ากับของกริดอินพุต