当前位置： 面试刷题>> 矩阵中的最长递增路径 (经典算法题500道)
### 题目描述补充
给定一个整数矩阵 `matrix`，找出其中最长递增路径的长度。递增路径定义为：从矩阵中的某个位置 `(r, c)` 可以移动到 `(r+1, c)`、`(r-1, c)`、`(r, c+1)` 或 `(r, c-1)`（如果目标位置在矩阵的边界内且值比当前位置的值大）。
### 示例
输入：
```
matrix = [
[9,9,4],
[6,6,8],
[2,1,1]
]
```
输出：4
解释：最长递增路径为 `[1, 2, 6, 9]` 或 `[1, 2, 6, 8]`。
### PHP 代码示例
```php
function longestIncreasingPath($matrix) {
if (empty($matrix)) return 0;
$rows = count($matrix);
$cols = count($matrix[0]);
$memo = array_fill(0, $rows, array_fill(0, $cols, 0)); // 用于存储已计算的路径长度
$maxLen = 0;
for ($i = 0; $i < $rows; $i++) {
for ($j = 0; $j < $cols; $j++) {
$maxLen = max($maxLen, dfs($matrix, $i, $j, $memo, $rows, $cols));
}
}
return $maxLen;
}
function dfs($matrix, $row, $col, &$memo, $rows, $cols) {
if ($memo[$row][$col] > 0) return $memo[$row][$col]; // 如果已经计算过，直接返回结果
$directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]; // 右，左，下，上
$maxLength = 1;
foreach ($directions as $dir) {
$newRow = $row + $dir[0];
$newCol = $col + $dir[1];
if ($newRow >= 0 && $newRow < $rows && $newCol >= 0 && $newCol < $cols && $matrix[$newRow][$newCol] > $matrix[$row][$col]) {
$maxLength = max($maxLength, 1 + dfs($matrix, $newRow, $newCol, $memo, $rows, $cols));
}
}
$memo[$row][$col] = $maxLength; // 缓存结果
return $maxLength;
}
// 示例用法
$matrix = [
[9,9,4],
[6,6,8],
[2,1,1]
];
echo longestIncreasingPath($matrix); // 输出 4
```
### Python 代码示例
```python
def longestIncreasingPath(matrix):
if not matrix:
return 0
rows, cols = len(matrix), len(matrix[0])
memo = [[0] * cols for _ in range(rows)]
max_len = 0
def dfs(r, c):
if memo[r][c] > 0:
return memo[r][c]
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
max_length = 1
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
max_length = max(max_length, 1 + dfs(nr, nc))
memo[r][c] = max_length
return max_length
for i in range(rows):
for j in range(cols):
max_len = max(max_len, dfs(i, j))
return max_len
# 示例用法
matrix = [
[9,9,4],
[6,6,8],
[2,1,1]
]
print(longestIncreasingPath(matrix)) # 输出 4
```
### JavaScript 代码示例
```javascript
function longestIncreasingPath(matrix) {
if (!matrix.length) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
const memo = Array.from({length: rows}, () => Array(cols).fill(0));
let maxLen = 0;
function dfs(r, c) {
if (memo[r][c] > 0) return memo[r][c];
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
let maxLength = 1;
for (const [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c]) {
maxLength = Math.max(maxLength, 1 + dfs(nr, nc));
}
}
memo[r][c] = maxLength;
return maxLength;
}
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
maxLen = Math.max(maxLen, dfs(i, j));
}
}
return maxLen;
}
// 示例用法
const matrix = [
[9,9,4],
[6,6,8],
[2,1,1]
];
console.log(longestIncreasingPath(matrix)); // 输出 4
```
码小课网站中有更多关于算法和数据结构的内容分享给大家学习，欢迎访问并深入学习！