Pythonのマトリックスで最長増加パス

1つの行列があるとします。最長増加経路の長さを見つける必要があります。各セルから、左、右、上、下の4つの方向に移動できます。斜めに移動したり、境界の外に移動したりすることはできません。

したがって、入力が次のような場合

その場合、最長増加パスは[3、4、5、6]であるため、出力は4になります。

これを解決するには、次の手順に従います-

• 関数solve（）を定義します。これにはi、j、matrixが必要です

• dp [i、j]がゼロ以外の場合、

  • dp [i、j]

    を返します

• dp [i、j]：=1

• temp：=0

• i-1からi+2の範囲のrについては、次のようにします

  • j-1からj+2の範囲のcについては、次のようにします

    • rがiと同じで、cがjと同じであるか、（| r-i |が1と同じで、| c-j |が1と同じである）場合、

      • 次のイテレーションに行く

    • c> =0かつr>=0かつr<行列の行数およびc<行列の列サイズ[0]および行列[r、c]>行列[i、j]の場合、

      • temp：=tempの最大値、solve（r、c、matrix）

• dp [i、j]：=dp [i、j] + temp

• dp [i、j]

  を返します

• メインの方法から、次のようにします-

• 行列がゼロ以外の場合、

  • 0を返す

• dp：=与えられた行列と同じサイズの行列で、0で埋めます

• ans：=0

• 0から行列のサイズまでの範囲のiについては、次のようにします

  • 0からmatrix[0]のサイズまでの範囲のjの場合、実行

    • dp [i、j]が0と同じ場合、

      • 解決（i、j、行列）

• ansを返す

例

理解を深めるために、次の実装を見てみましょう-

class Solution(object):
   def solve(self,i,j,matrix):
      if self.dp[i][j]:
         return self.dp[i][j]
      self.dp[i][j] = 1
      temp = 0
      for r in range(i-1,i+2):
         for c in range(j-1,j+2):
            if r==i and c==j or (abs(r-i)==1 and abs(c-j)==1):
               continue
            if c>=0 and r>=0 and r<len(matrix) and c<len(matrix[0]) and matrix[r][c]>matrix[i][j]:
temp = max(temp,self.solve(r,c,matrix))
               self.dp[i][j]+=temp
               return self.dp[i][j]
   def longestIncreasingPath(self, matrix):
      if not matrix:
         return 0
      self.dp = [ [0 for i in range(len(matrix[0]))] for j in range(len(matrix))]
      self.ans = 0
      for i in range(len(matrix)):
         for j in range(len(matrix[0])):
            if self.dp[i][j]==0:
               self.solve(i,j,matrix)
            self.ans = max(self.ans,self.dp[i][j])
      return self.ans

ob = Solution()
print(ob.longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]))

入力

[[9,9,4],[6,6,8],[2,1,1]]

出力

4