LeetCode LIS系列 (Longest Increasing Path in a Matrix)

类似的东西还有：
674. Longest Continuous Increasing Subsequence
https://leetcode.com/problems/longest-continuous-increasing-subsequence/description/
300. Longest Increasing Subsequence
https://leetcode.com/problems/longest-increasing-subsequence/description/
longest path increasing by 1
https://www.geeksforgeeks.org/find-the-longest-path-in-a-matrix-with-given-constraints/
 
下面的代码是这个题的：

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/ 
主要思路就是瞎JB搜索，不过某一个位置的结果可以记录下来给后续的重复搜索使用。

class Solution {
public:
	int subLIP(vector<vector<int>>& matrix, vector<vector<int>>& sub_results, int row, int col)
	{
		if (row < 0 || row >= matrix.size())
			return 0;
		if (col < 0 || col >= matrix[0].size())
			return 0;
		if (sub_results[row][col] != -1)
			return sub_results[row][col];
		// go left
		int maxResult = -1;
		if (col > 0 && matrix[row][col - 1] > matrix[row][col])
			maxResult = max(maxResult, 1 + subLIP(matrix, sub_results, row, col - 1));
		// go right
		if (col < matrix[0].size() - 1 && matrix[row][col + 1] > matrix[row][col])
			maxResult = max(maxResult, 1 + subLIP(matrix, sub_results, row, col + 1));
		// go up
		if (row > 0 && matrix[row - 1][col] > matrix[row][col])
			maxResult = max(maxResult, 1 + subLIP(matrix, sub_results, row - 1, col));
		// go down
		if (row < matrix.size() - 1 && matrix[row + 1][col] > matrix[row][col])
			maxResult = max(maxResult, 1 + subLIP(matrix, sub_results, row + 1, col));
		sub_results[row][col] = max(1, maxResult);
		return sub_results[row][col];
	}
	int longestIncreasingPath(vector<vector<int>>& matrix) {
		vector<vector<int>> sub_results;
		sub_results.resize(matrix.size());
		for (int i = 0; i < matrix.size(); ++i)
		{
			sub_results[i].resize(matrix[0].size(), -1);   // -1 means unknown
		}
		int result = 0;
		for (int r = 0; r < matrix.size(); ++r)
		{
			for (int c = 0; c < matrix[r].size(); ++c)
			{
				result = max(result, subLIP(matrix, sub_results, r, c));
			}
		}
		return result;
	}
};