LeetCode题目链接329. Longest Increasing Path in a Matrix

2017/04/01 Algorithm

tips:记忆化搜索的经典题目,分析与DP的关系

LeetCode 题目链接:329. Longest Increasing Path in a Matrix

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).

Example 1:

nums = [[9,9,4],[6,6,8],[2,1,1]]

Return 4 The longest increasing path is [1, 2, 6, 9].

Example 2: nums = [[3,4,5],[3,2,6],[2,2,1]]

Return 4 The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

分析

容易想到用深度优先搜索解决该问题,伪代码如下:

res <= 0
for i <= 1 to matrix.length do
	for j <= 1 to matrix[0].length do
		res <= max(res,DFS(i,j));
return res
其中DFS伪代码:

DFS(i,j) 
    directions <= {0,1},{0,-1},{1,0},{-1,0}
	ret <= 0

	for k <= 0 to 4 do
		indexi <= i + directions[k][0]
		indexj <= j + directions[k][1]

		if matrix[indexi][indexj] > maxtrix[i][j]
			ret <= max(ret,DFS(indexi,indexj) + 1)
	return ret 

然后,仔细DFS,容易发现,存在大量的重复问题,同一个i,j可能被多次搜索到,因此我们用一个数组记录已经搜索过的元素,避免重复子问题,又称为记忆化搜索,如下:

for i <- 0 to matrix.length do
	for j <- 0 to matrix[0].length do
		value[i][j] <- 0

DFS(i,j) 
	if value[i][j] != 0
		return value[i][j];

    directions <- {0,1},{0,-1},{1,0},{-1,0}
	ret <- 0

	for k <- 0 to 4 do
		indexi <- i + directions[k][0]
		indexj <- j + directions[k][1]

		if matrix[indexi][indexj] > maxtrix[i][j]
			ret <- max(ret,DFS(indexi,indexj) + 1)
	return ret 

tips:动态规划和记忆化搜索有着很紧密的联系,显然所有的动态规划可以很容易的用记忆化搜索的形式写出来,但是效率会变低,因为增加了很多函数调用的过程,压栈弹栈会消耗时间,很多OJ动态规划题目写成记忆化搜索后会TLE。然而,有些记忆化搜索不能(也许可以,至少很难)写成动态规划的形式。我有一个不够严谨但是相对直观的总结如下,望轻批…

动态规划一定是在原问题的所有更小规模子问题都有了答案后,挑出所有子问题的最优答案即可得到原问题的答案,因此可以将问题规模不断变小,直至规约成一个非常简单的问题(初始条件),从而得到原始问题的解。对于记忆化搜索而言,原问题的解可以在得到所有子问题的最优解后得到,但是子问题在规模上并不比原问题小,大部分情况是和原问题等同的问题,本题就是一个例子。这种情况下,我们无法让问题的规模一直变小,当然也不可能规约成一个非常简单的问题,因此我们不知道该率先解决哪个问题(动态规划一定是率先解决初始问题),但是我们可以确定他们之间存在大量重复问题,因此,我们按照某个顺序(如本题按照矩阵遍历的顺序)依次解决问题,每解决一个问题就将其答案记录下来,后期再遇到同一个问题就无需重复解决,从而降低问题复杂度。所以,动态规划和记忆化搜索都是通过避免解决重复的问题来减小问题复杂度,只是动态规划的子问题规模在不断减小,因此整个过程问题规模具有方向性,而记忆化搜索问题规模并没有方向性.

源代码

public class Solution {
	private int[][] value; //记录已经解决的问题的解
	private int[][] matrix;
	
	private int DFS(int i,int j){
		if(value[i][j] != 0){ //已经解决过的问题,无需重复解决
			return value[i][j];
		}
		//没有解决过的问题
		int[][] directions = \{\{0,1\},\{0,-1\},\{1,0\},\{-1,0\}\};
		
		int res = 1;
		for(int k = 0; k < directions.length; k++){
			int indexi = i + directions[k][0];
			int indexj = j + directions[k][1];
			
			if(indexi >= 0 && indexi < matrix.length && indexj >= 0 && indexj < matrix[0].length 
					&& matrix[indexi][indexj] > matrix[i][j]){
				res = Math.max(res, DFS(indexi,indexj) + 1);
			}
		}
		//记录该问题答案,供其他问题使用
		value[i][j] = res;
		return res;
	}
	
    public int longestIncreasingPath(int[][] matrix) {
    	if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0){
    		return 0;
    	}
    	
    	this.matrix = matrix;
    	value = new int[matrix.length][matrix[0].length];
    	
    	//按照矩阵遍历的顺序依次解决每个问题
    	int ret = 0;
    	for(int i = 0; i < matrix.length; i++){
    		for(int j = 0; j < matrix[0].length; j++){
    			
    			DFS(i,j);
    			
    			if(value[i][j] > ret){
    				ret = value[i][j];
    			}
    		}
    	}
    	
    	return ret;	        
    }
}

Search

    Table of Contents