행렬에서 가장 긴 증가 경로
m x n
정수 matrix
가 주어지면 matrix
에서 가장 긴 증가 경로의 길이를 반환합니다.각 셀에서 왼쪽, 오른쪽, 위 또는 아래의 네 방향으로 이동할 수 있습니다. 대각선으로 이동하거나 경계 밖으로 이동할 수 없습니다(즉, 랩 어라운드는 허용되지 않음).
예 1:
입력: 행렬 = [[9,9,4],[6,6,8],[2,1,1]]
출력: 4
설명: 가장 긴 증가 경로는
[1, 2, 6, 9]
입니다.예 2:
입력: 행렬 = [[3,4,5],[3,2,6],[2,2,1]]
출력: 4
설명: 가장 긴 증가 경로는
[3, 4, 5, 6]
입니다. 대각선 이동은 허용되지 않습니다.예 3:
입력: 행렬 = [[1]]
출력: 1
제약:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 - 1
해결책:
class Solution:
def getNeighbours(self, i, j, m, n):
for x, y in [(i - 1, j), (i, j + 1), (i + 1, j), (i, j - 1)]:
if 0 <= x < m and 0 <= y < n:
yield (x, y)
def longestTill(self, matrix, i, j, m, n):
if (i, j) in self.cache:
return self.cache[(i, j)]
mlen = 1
for x, y in self.getNeighbours(i, j, m, n):
if matrix[x][y] > matrix[i][j]:
curr = 1 + self.longestTill(matrix, x, y, m, n)
mlen = max(mlen, curr)
self.cache[(i, j)] = mlen
return mlen
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
m = len(matrix)
n = len(matrix[0])
mlen = 1
self.cache = {}
for i in range(m):
for j in range(n):
if (i, j) not in self.cache:
curr = self.longestTill(matrix, i, j, m, n)
mlen = max(mlen, curr)
return mlen
Reference
이 문제에 관하여(행렬에서 가장 긴 증가 경로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/theabbie/longest-increasing-path-in-a-matrix-13k8텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)