Python의 행렬에서 가장 긴 증가 경로

<시간/>

하나의 행렬이 있다고 가정합니다. 가장 긴 증가 경로의 길이를 찾아야 합니다. 각 셀에서 왼쪽, 오른쪽, 위 또는 아래의 네 가지 방향으로 이동할 수 있습니다. 대각선으로 이동하거나 경계 밖으로 이동할 수 없습니다.

따라서 입력이 다음과 같으면

9	9	4
6	6	8
2	1	1

가장 긴 증가 경로가 [3, 4, 5, 6]이므로 출력은 4가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

함수 solve()를 정의합니다. 이것은 i,j,matrix가 필요합니다.
dp[i,j]가 0이 아니면
- 반환 dp[i, j]
dp[i, j] :=1
온도 :=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 :=최대 온도, solve(r, c, matrix)
dp[i, j] :=dp[i, j] + 온도
반환 dp[i, j]
주요 방법에서 다음을 수행하십시오 -
행렬이 0이 아닌 경우
- 0 반환
dp :=주어진 행렬과 크기가 같고 0으로 채워지는 행렬
답변 :=0
범위 0에서 행렬 크기까지의 i에 대해
- 범위 0에서 행렬[0]의 크기에 있는 j에 대해
  - dp[i, j]가 0과 같으면
    - 해결(i, j, 행렬)
반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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]]