6/24, 记忆化搜索

Longest Increasing Continuous Subsequence

从左到右扫一遍，再从右往左扫一遍就可以了。。。这题只是后面记忆化搜索的引子。

public class Solution {
    /**
     * @param A an array of Integer
     * @return  an integer
     */
    public int longestIncreasingContinuousSubsequence(int[] A) {
        // Write your code here
        if(A == null || A.length == 0) return 0;
        int max = 1;
        int cur = 1;
        for(int i = 1; i < A.length; i++){
            if(A[i] > A[i - 1]){
                cur ++;
                max = Math.max(max, cur);
            } else {
                cur = 1;
            }
        }

        cur = 1;
        for(int i = A.length - 2; i >= 0; i--){
            if(A[i] > A[i + 1]){
                cur ++;
                max = Math.max(max, cur);
            } else {
                cur = 1;
            }
        }

        return max;
    }
}

Longest Increasing Path in a Matrix

去年的 Google 高频题，著名的 POJ 1088 - 滑雪。当时在论坛里看到这道题的时候，觉得完全没思路，也不知道自己什么时候能独立当场把这道题做出来。

如今一次AC的感觉，真爽啊。

这题是 2D-array 上的搜索问题，参考 number of islands 和 word search.

• Optimal Substructure

  • 全局最优解一定由从起点 maxPath(i , j) 和其相邻的有效起点 maxPath(i', j') 的 subproblem 构造而成

  • 由于最优解 path 对单调性有要求，因此无需修改原矩阵，也无需担心下一个位置回头造成死循环

• Overlap Subproblems

  • 对于每一个起点 maxPath(i , j) ，都需要 top-bottom 的递归解决其下一个有效位置 maxPath(i', j') 的子问题，并且高度覆盖。

public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] dp = new int[rows * cols];

        int max = 0;
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                max = Math.max(max, memoizedSearch(i, j, cols, rows, matrix, dp));
            }
        }

        return max;
    }

    private int memoizedSearch(int x, int y, int cols, int rows, 
                               int[][] matrix, int[] dp){
        if(x < 0 || x >= rows) return 0;
        if(y < 0 || y >= cols) return 0;

        int index = x * cols + y;
        if(dp[index] != 0) return dp[index];

        int left = 0, right = 0;
        int top = 0, bottom = 0;

        if(y - 1 >= 0 && matrix[x][y - 1] > matrix[x][y]) left = memoizedSearch(x, y - 1, cols, rows, matrix, dp);
        if(y + 1 < cols && matrix[x][y + 1] > matrix[x][y]) right = memoizedSearch(x, y + 1, cols, rows, matrix, dp);
        if(x - 1 >= 0 && matrix[x - 1][y] > matrix[x][y]) top = memoizedSearch(x - 1, y, cols, rows, matrix, dp);
        if(x + 1 < rows && matrix[x + 1][y] > matrix[x][y]) bottom =memoizedSearch(x + 1, y, cols, rows, matrix, dp);

        int maxLR = Math.max(left, right) + 1; 
        int maxTB = Math.max(top, bottom) + 1;
        int max = Math.max(maxLR, maxTB);

        dp[index] = max;

        return max;
    }
}