Leetcode(329) Longest Increasing Path in a Matrix

Description:

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:

Input: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

解法：

首先自然而然地想到了对于每一个点采用深度优先的搜索算法，得到以该点为起点的最长路径，然而在这个过程中，其实存在重复搜索的问题而影响了程序的效率。代码跑出来果然超时了。以下为DFS代码：

public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int max = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int cnt = dfs(i, j, matrix, row, col);
                if (cnt > max) {
                    max = cnt;
                }
            }
        }
        return max;
    }

    private int dfs(int i, int j, int[][] matrix, int row, int col) {
        Stack s = new Stack();
        node start = new node(i, j, matrix[i][j],1);
        s.push(start);
        node now = start;
        int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int cnt = 0;
        while (!s.isEmpty()) {
            now = (node) s.pop();
            int flag = 0;
            for (int ii = 0; ii < 4; ii++) {
                node next = new node(now.i+ direction[ii][0], now.j + direction[ii][1], -1,1);
                if (isvalid(next, row, col) && matrix[next.i][next.j] > now.value) {
                    next.value = matrix[next.i][next.j];
                    next.step = now.step + 1;
                    s.push(next);
                    flag = 1;
                }
            }
            if(flag == 0){
                if(now.step > cnt){
                    cnt = now.step;
                }
            }
        }
        return cnt;
    }

    private boolean isvalid(node n, int row, int col) {
        if (n.i >= 0 && n.i < row && n.j >= 0 && n.j < col ) {
            return true;
        }
        return false;
    }

}

class node {
    int i;
    int j;
    int value;
    int step = 1;

    node(int i, int j, int value,int step) {
        this.i = i;
        this.j = j;
        this.value = value;
        this.step = step;
    }
}

为解决重复搜索问题，引入动态规划思想，以空间换时间。引入记忆矩阵，改写DFS搜索方法，采用递归的方式进行搜索。代码如下：

public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int memory[][] = new int[row][col];
        int max = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int cnt = dfs(i, j, matrix, row, col,memory);
                if (cnt > max) {
                    max = cnt;
                }
            }
        }
        return max;
    }

    private int dfs(int i, int j, int[][] matrix, int row, int col,int[][] memory) {
        int maxstep = 1;
        if(memory[i][j]>0){
            return memory[i][j];
        }
        node now = new node(i,j,matrix[i][j],0);
        int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int ii = 0; ii < 4; ii++){
            node next = new node(now.i+ direction[ii][0], now.j + direction[ii][1], -1,1);
            if (isvalid(next, row, col) && matrix[next.i][next.j] > now.value){
                next.value = matrix[next.i][next.j];
                int cal = dfs(next.i,next.j,matrix,row,col,memory) + 1;
                if(maxstep < cal){
                    maxstep = cal;
                }
            }
        }
        memory[i][j] = maxstep;
        return memory[i][j];
    }

    private boolean isvalid(node n, int row, int col) {
        if (n.i >= 0 && n.i < row && n.j >= 0 && n.j < col ) {
            return true;
        }
        return false;
    }

}

class node {
    int i;
    int j;
    int value;
    int step = 1;

    node(int i, int j, int value,int step) {
        this.i = i;
        this.j = j;
        this.value = value;
        this.step = step;
    }
}

又重写了一遍，这次顺多了

class Solution {
    int[] dirx = {-1, 1, 0, 0};
    int[] diry = {0, 0, 1, -1};

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int[][] dp = new int[matrix.length][matrix[0].length];
        int res = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                DFS(i, j, matrix, dp, 1);
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (res < dp[i][j]) {
                    res = dp[i][j];
                }
            }
        }
        return res;
    }

    void DFS(int x, int y, int[][] matrix, int[][] dp, int step) {
        if (dp[x][y] > step && step != 0) {
            return;
        }
        dp[x][y] = step;
        for (int i = 0; i < 4; i++) {
            int nextx = x + dirx[i];
            int nexty = y + diry[i];
            if (nextx >= 0 && nextx < matrix.length && nexty >= 0 && nexty < matrix[0].length && dp[nextx][nexty] < step + 1 && matrix[nextx][nexty] > matrix[x][y]) {
                DFS(nextx, nexty, matrix, dp, step + 1);
            }
        }
    }
}