问题描述
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).
想法与实现
这道题一开始看到就直接想用深度优先搜索来实现，没什么想不出的地方。
class Solution {
private:
int max;
vector<vector<bool>> flag;
int sizeX;
int sizeY;
bool isValid(int i, int j) {
if (i >= 0 && i < sizeX && j >= 0 && j < sizeY) {
return true;
} else {
return false;
}
}
void dfs(vector<vector<int>>& matrix, int posX, int posY, int sum) {
if (flag[posX][posY] == true) {
flag[posX][posY] = false;
sum++;
vector<vector<int>> dirs = {
{-1, 0},
{1, 0},
{0, -1},
{0, 1}
};
int sz = dirs.size();
for (int i = 0; i < sz; i++) {
int newPosX = posX + dirs[i][0];
int newPosY = posY + dirs[i][1];
if (isValid(newPosX, newPosY) && flag[newPosX][newPosY] == true &&
matrix[posX][posY] < matrix[newPosX][newPosY]) {
dfs(matrix, newPosX, newPosY, sum);
}
}
if (sum > max) {
max = sum;
}
flag[posX][posY] = true;
return;
}
}
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
max = 0;
sizeX = matrix.size();
sizeY = matrix[0].size();
flag = vector<vector<bool>>(sizeX, vector<bool>(sizeY, true));
for (int i = 0; i < sizeX; i++) {
for (int j = 0; j < sizeY; j++) {
dfs(matrix, i, j, 0);
}
}
return max;
}
};
但是在写完后会发现，这样写是超时的。这时候就要基于观察，来优化一下。在深度优先搜索中，做了很多无用功，对于每个点，都会执行很多次dfs函数，因此可以Memo的方式，来缓存每次执行的结果，由此就不需要多次计算。
class Solution {
private:
int max;
vector<vector<int>> flag;
int sizeX;
int sizeY;
bool isValid(int i, int j) {
if (i >= 0 && i < sizeX && j >= 0 && j < sizeY) {
return true;
} else {
return false;
}
}
int getMax(int a, int b) {
if (a > b) {
return a;
} else {
return b;
}
}
int dfs(vector<vector<int>>& matrix, int posX, int posY) {
if (flag[posX][posY] == 0) {
int sum = 0;
vector<vector<int>> dirs = {
{-1, 0},
{1, 0},
{0, -1},
{0, 1}
};
int sz = dirs.size();
for (int i = 0; i < sz; i++) {
int newPosX = posX + dirs[i][0];
int newPosY = posY + dirs[i][1];
if (isValid(newPosX, newPosY) &&
matrix[posX][posY] < matrix[newPosX][newPosY]) {
sum = getMax(dfs(matrix, newPosX, newPosY), sum);
}
}
flag[posX][posY] = sum + 1;
return sum + 1;
} else {
return flag[posX][posY];
}
}
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
max = 0;
sizeX = matrix.size();
if (sizeX == 0) {
return max;
}
sizeY = matrix[0].size();
if (sizeY == 0) {
return max;
}
flag = vector<vector<int>>(sizeX, vector<int>(sizeY, 0));
for (int i = 0; i < sizeX; i++) {
for (int j = 0; j < sizeY; j++) {
max = getMax(max, dfs(matrix, i, j));
}
}
return max;
}
};