题目描述
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example1:
Input: nums = [ [9,9,4], [6,6,8], [2,1,1] ] Output: 4 Explanation: The longest increasing path is [1, 2, 6, 9].
Example2:
Input: nums = [ [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.
NOTE
- All inputs are consist of lowercase letters a-z.
- The values of words are distinct.
解题思路
- dfs
- 使用dp记忆化搜索
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int res = 1;
int row = matrix.size();
if(row == 0){
return 0;
}
int col = matrix[0].size();
vector<vector<int>> dp(row, vector<int>(col, -1));
int ans = 0;
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(dp[i][j] == -1){
ans = max(ans, dfs(i, j, row, col, matrix, INT_MIN, dp));
}
}
}
return ans;
}
int dfs(int r, int c, int row, int col, vector<vector<int>>&matrix, int num, vector<vector<int>>& dp){
if(r < 0 || r >= row || c < 0 || c >= col || matrix[r][c] <= num){
return 0;
}
if(dp[r][c] != -1){
return dp[r][c];
}
int q1 = 1 + dfs(r + 1, c, row, col, matrix, matrix[r][c], dp);
int q2 = 1 + dfs(r - 1, c, row, col, matrix, matrix[r][c], dp);
int q3 = 1 + dfs(r, c + 1, row, col, matrix, matrix[r][c], dp);
int q4 = 1 + dfs(r, c - 1, row, col, matrix, matrix[r][c], dp);
dp[r][c] = max(q1, max(q2, max(q3, q4))); // 这里取四个方向的最大值 作为dp返回的结果
return dp[r][c];
}
};
