心似双丝网
中有千千结
虽然是每天刷一道题，但好几次都没时间写题解。。。
这道题算是dp的一种，一般从暴力的角度出发很容易想到dfs能直接获得每个点作为起始点得到的最长递增路径。
这样的话，对着每个点做一次暴力dfs，就得到答案了。
不过显然这样子会超时，复杂度差不多O((m * n)^2)。。。
仔细想想实际上，dfs在经过每个点的时候，无论是不是从这个点开始的，都能得到从这个点出发的最长递增路径。于是“记忆化搜索”这个东西就来了。
可以利用二维数组记住每次dfs到的点的最长递增路径，这样下次递归到这个点的时候，就不用再接着递归了。
class Solution {
private:
static int dx[];
static int dy[];
inline bool check(vector<vector<int>> &g, int i, int j, int pre) {
int m = g.size(), n = g[0].size();
return 0 <= i && i < m && 0 <= j && j < n && pre < g[i][j];
}
int dfs(vector<vector<int>> &g, int x, int y, vector<vector<int>> &dist) {
if (dist[x][y] != 0) return dist[x][y];
dist[x][y] = 1;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (check(g, xx, yy, g[x][y])) {
dist[x][y] = max(dist[x][y], 1 + dfs(g, xx, yy, dist));
}
}
return dist[x][y];
}
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
vector<vector<int>> dist(m, vector<int>(n, 0));
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] == 0)
ans = max(ans, dfs(matrix, i, j, dist));
}
}
return ans;
}
};
int Solution::dx[] = {0, 0, 1, -1};
int Solution::dy[] = {1, -1, 0, 0};
