LeetCode 329. 행렬 의 최 장 증가 경로 (역 추적 또는 토폴로지 정렬 + 동적 계획)
10145 단어 LeetCode알고리즘 --- - DP
정수 행렬 을 지정 하여 최 장 증가 경로 의 길 이 를 찾 습 니 다.
각 칸 에 대해 서 는 위, 아래, 왼쪽, 오른쪽 네 방향 으로 이동 할 수 있 습 니 다.대각선 방향 으로 이동 하거나 경계 밖으로 이동 할 수 없습니다.
1:
: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
: 4
: [1, 2, 6, 9]。
2:
: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
: 4
: [3, 4, 5, 6]。 。
: (LeetCode)
:https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix
。 , 。
솔 루 션 1 역 추적
비망록 을 챙 겨 야 합 니 다.해제
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix or not matrix[0]: return 0
row = len(matrix)
col = len(matrix[0])
lookup = [[0] * col for _ in range(row)]
def dfs(i, j):
if lookup[i][j] != 0:
return lookup[i][j]
#
res = 1
for x, y in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
tmp_i = x + i
tmp_j = y + j
if 0 <= tmp_i < row and 0 <= tmp_j < col and \
matrix[tmp_i][tmp_j] > matrix[i][j]:
res = max(res, 1 + dfs(tmp_i, tmp_j))
lookup[i][j] = max(res, lookup[i][j])
#
# val = matrix[i][j]
# lookup[i][j] = 1 + max(
# dfs(i + 1, j) if 0 <= i + 1 < row and 0 <= j < col and matrix[i + 1][j] > val else 0,
# dfs(i - 1, j) if 0 <= i - 1 < row and 0 <= j < col and matrix[i - 1][j] > val else 0,
# dfs(i, j + 1) if 0 <= i < row and 0 <= j + 1 < col and matrix[i][j + 1] > val else 0,
# dfs(i, j - 1) if 0 <= i < row and 0 <= j - 1 < col and matrix[i][j - 1] > val else 0,
# )
#
# lookup[i][j] = 1 + max(
# [dfs(i + x, y + j) for x, y in [[-1, 0], [1, 0], [0, 1], [0, -1]] \
# if 0 <= (i + x) < row and 0 <= (j + y) < col and matrix[i + x][j + y] > matrix[i][j]] or [0]
# )
return lookup[i][j]
return max(dfs(i, j) for i in range(row) for j in range(col))
:powcai
:https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/dfsji-chong-xie-fa-by-powcai/
: (LeetCode)
。 , 。
Solution 2 토폴로지 정렬 + 동적 계획
문 제 는 토폴로지 정렬 로 동적 계획 의 시작 점 을 찾 아 낮은 점 에서 상태 이전 을 한다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.