329. Longest Increasing Path in a Matrix
Đề Bài
Given an m x n integers matrix, return the length of the longest increasing path in matrix.
From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
Example 1:
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:
Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
Example 3:
Input: matrix = [[1]] Output: 1
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 231 - 1
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n×m)
💾 Không gian
O(n×m)
Lời Giải
Python
0329-longest-increasing-path-in-a-matrix.py
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
r, c = len(matrix), len(matrix[0])
dp = [[0 for _ in range(c)] for _ in range(r)]
DIR = [-1, 0, 1, 0, -1]
def dfs(x, y):
if dp[x][y] != 0:
return dp[x][y]
ans = 1
for i in range(4):
nx = x + DIR[i]
ny = y + DIR[i + 1]
if 0 <= nx < r and 0 <= ny < c:
if matrix[x][y] < matrix[nx][ny]:
ans = max(ans, 1 + dfs(nx, ny))
dp[x][y] = ans
return ans
ans = 0
for x in range(r):
for y in range(c):
ans = max(ans, dfs(x, y))
return ans