Google8.6 热滚滚的面经

楼主前段时间又做了下，感觉和lc word search那道题有点类似，用backtracking做了下，大家看看对不对？
import java.util.*;
public class solution {
    public int exist(int[][] board) {
        if(board==null){
            return 0;
        }
        int max=0;
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                    int len=helper(board, i, j, board[i][j], 0);
                max=Math.max(max, len);
            }
        }
        return max;
    }
    private int helper(int[][] board, int i, int j, int val, int len){
        
        if(i<0 || i>=board.length || j<0 || j>=board[0].length || board[i][j]!=val){
            return len;
        }
        len++;
        int l1=helper(board,i+1,j,val+1,len);
        int l2=helper(board,i-1,j,val+1,len);
        int l3=helper(board,i,j+1,val+1,len);
        int l4=helper(board,i,j-1,val+1,len);
        len=Math.max(l1, l2);
        len=Math.max(len, l3);
        len=Math.max(len, l4);
        return len;
    }
}

每个点计算一个可以到达的最大长度，然后维护一个最大长度。
如果当前值的上下左右有可以往下走的，len++，然后从下一个点开始继续走；走不下去就return当前的长度；

lyj87372517 发表于 2015-9-30 12:18
每个点计算一个可以到达的最大长度，然后维护一个最大长度。
如果当前值的上下左右有可以往下走的，len++ ...

这样递归复杂度太高了。。记下遍历到的每个节点的最大值
class Solution2 {
        int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        private int dfs(int[][] matrix, int posj, int posi, int[][] dp) {
                if (dp[posj][posi] != 0) {
                        return dp[posj][posi];
                }
                for (int k = 0; k < 4; k++) {
                        int j = posj+dir[k][0], i = posi+dir[k][1];
                        if (j < 0 || j >= matrix.length || i < 0 || i >= matrix[0].length) {
                                continue;
                        }
                        if (matrix[j][i] == matrix[posj][posi]+1) {
                                dp[posj][posi] = Math.max(dp[posj][posi], 1+dfs(matrix, j, i, dp));
                        }
                }
                if (dp[posj][posi] == 0) {
                        dp[posj][posi] = 1;
                }
                return dp[posj][posi];
        }
       
        public int getMaxLen(int[][] matrix) {
                if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                        return 0;
                }
                int wid = matrix.length, len = matrix[0].length;
                int[][] dp = new int[wid][len];
                int max = 0;
                for (int j = 0; j < wid; j++) {
                        for (int i = 0; i < len; i++) {
                                if (dp[j][i] == 0) {
                                        dfs(matrix, j, i, dp);
                                }
                                if (dp[j][i] > max) {
                                        max = dp[j][i];
                                }
                        }
                }
                return max;
        }
}

how about this: 开两个dp矩阵。一个矩阵climbup[][]用来记录每个点向高处走最高能走到多高，及走到极值的方向。另一个矩阵slidedown[][]用来记录每个点向低处走最低能走到多低，及走向极值的方向。用dfs+动态规划先填写整个climbup[][]，再填写整个slidedown[][]，然后求argmax(climbup[i][j]+slidedown[i][j])，找到最长路径上的任意一个点(i,j)，最后根据之前保存的极值方向，还原出整个路径。