最大長のスネークシーケンスを見つける


難易度 ハード
よく聞かれる Amazon (アマゾン) コードネーション エクスペディア 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

説明

最大長のスネークシーケンスを見つける

アプローチ

問題は、最大長のスネークシーケンスを見つけることを求めており、入力としてグリッドが提供されています。 ナイーブまたはブルートフォースのアプローチは、グリッドの左上隅から開始することであり、再帰の使用はその右下の隣を通過します。 同様に、それらのセルから隣接するセルに移動し、条件が課せられているために前進することができないようなセルが見つかるまで続きます。 一般にXNUMXつの再帰呼び出しがある再帰を使用すると、時間計算量が高くなります。

上記のアプローチの代わりに、 動的計画法 再帰的なソリューションを使用して問題を説明しているためです。 次に、ソリューションを最適化するためにメモ化するだけです。 上記のアプローチの時間計算量は指数関数的でしたが、 動的計画法 それを多項式に減らすことができます。 この問題では、最初に行インデックス、次に列インデックスのXNUMXつの状態を確認します。 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グリッドを作成するためです。