矩阵中的最长递增路径-记忆化搜索

矩阵中的最长递增路径

Solution

一个简单的dfs搜索问题，只需要改成一个带返回值的搜索即可，再加上一个缓存表优化即可通过。

#include<iostream>
#include<vector>
using namespace std;

//递归做法
//f(x,y)表示从(x,y)出发的最长递增路径长度
//由于这题的路径自带单调性，所以不需要设置标记数组
int f1(vector<vector<int>>& matrix, int x, int y) {
	int m = matrix.size();
	int n = matrix[0].size();
	if (x < 0 || x >= m || y < 0 || y >= n) return 0;
	int ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0;
	if (x + 1 < m && matrix[x + 1][y] > matrix[x][y]) ans1 = f1(matrix, x + 1, y);
	if (x - 1 >= 0 && matrix[x - 1][y] > matrix[x][y])ans2 = f1(matrix, x - 1, y);
	if (y + 1 < n && matrix[x][y + 1] > matrix[x][y]) ans3 = f1(matrix, x, y + 1);
	if (y - 1 >= 0 && matrix[x][y - 1] > matrix[x][y]) ans4 = f1(matrix, x, y - 1);
	return 1 + max(ans1, max(ans2, max(ans3, ans4)));
}

//带缓存表的递归
int f2(vector<vector<int>>& matrix, int x, int y, vector<vector<int>>& dp) {
	int m = matrix.size();
	int n = matrix[0].size();
	if (x < 0 || x >= m || y < 0 || y >= n) return 0;
	int ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0;
	if (dp[x][y] != -1) return dp[x][y];
	if (x + 1 < m && matrix[x + 1][y] > matrix[x][y]) ans1 = f2(matrix, x + 1, y, dp);
	if (x - 1 >= 0 && matrix[x - 1][y] > matrix[x][y])ans2 = f2(matrix, x - 1, y, dp);
	if (y + 1 < n && matrix[x][y + 1] > matrix[x][y]) ans3 = f2(matrix, x, y + 1, dp);
	if (y - 1 >= 0 && matrix[x][y - 1] > matrix[x][y]) ans4 = f2(matrix, x, y - 1, dp);
	int ans = 1 + max(ans1, max(ans2, max(ans3, ans4)));
	dp[x][y] = ans;
	return ans;
}
int longestIncreasingPath1(vector<vector<int>>& matrix) {
	int m = matrix.size();
	int n = matrix[0].size();
	int ans = 0;
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			ans = max(ans, f1(matrix, i, j));
		}
	}
	return ans;
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
	int m = matrix.size();
	int n = matrix[0].size();
	vector<vector<int>>dp(m + 1, vector<int>(n + 1, -1));
	int ans = 0;
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			ans = max(ans, f2(matrix, i, j, dp));
		}
	}
	return ans;
}

int main() {

	return 0;
}