记忆化搜索 (memorization)

• 动态规划的实现方式:
  • 循环(从小到大递推)
  • 记忆化搜索(从大到小搜索)
    • 画搜索树
    • 万金油

Longest Continuous Increasing Subsequence

general method, using two loops (or one loop) to address the problem, time complexity is O(n), and space complexity is O(1).

public int longestIncreasingContinuousSubsequence(int[] A) {
    // write your code here
    if (A == null || A.length == 0) return 0;

    int licsMax = 1, prev = A[0], lics = 1;   // note that, it should be initialized as 1.
    // ascending order
    // 5 6 3 2 1 
    for (int a : A) {
        lics = (prev < a) ? lics + 1 : 1;
        licsMax = Math.max(licsMax, lics);
        prev = a;
    }

    // reset
    lics = 1;
    prev = A[0];

    // descending order
    for (int a : A) {
        lics = (prev > a) ? lics + 1: 1;
        licsMax = Math.max(licsMax, lics);
        prev = a;
    }

    return licsMax;
}

Also, we can improve our solution using one loop. But this time, we use indices to record the start point and boolean variable to determine whether it is ascending or descending order.

public int longestIncreasingContinuousSubsequence(int[] A) {
    // write your code here
    if (A == null || A.length == 0) return 0;

    int licsMax = 1, start = 0;
    boolean ascending = false;

    for (int i = 1; i < A.length; i++) {
        if (A[i - 1] < A[i]) {
            // ascending order 
            if (!ascending) {       // means that it is a ascending order
                ascending = true;   // set as true
                start = i - 1;
            }
        } else if (A[i - 1] > A[i]) {
            // descending order
            if (ascending) {        // means that it is a ascending order
                ascending = false;  // set as false
                start = i - 1;
            }
        } else {
            start = i - 1;
        }
        licsMax = Math.max(licsMax, i - start + 1);
    }

    return licsMax;
}

think further, we can use memorization DP to address this problem, which would cause stack overflow, but shed some light on the search problem over the array. Time complexity is O(n), and space complexity is O(n)

public int longestIncreasingContinuousSubsequence(int[] A) {
    // write your code here

    if (A == null || A.length == 0) return 0;

    int lics = 0;
    int[] dp = new int[A.length];
    for (int i = 0; i < A.length; ++i) {
        if (dp[i] == 0) {
            lics = Math.max(lics, dfs(A, i, dp));
        }
    }
    return lics;
}

private int dfs(int[] A, int i, int[] dp) {
    if (dp[i] != 0) return dp[i];

    int left = 0, right = 0;
    // increasing from right to left
    if (i > 0 && A[i - 1] > A[i]) left = dfs(A, i - 1, dp);
    // increasing from left to right
    if (i + 1 < A.length && A[i+1] > A[i]) right = dfs(A, i + 1, dp);

    dp[i] = 1 + Math.max(left, right);
    return dp[i];
}

dfs 中使用记忆化存储避免重复递归，分左右两个方向递增，最后取较大值。这种方法对于数组长度较长时栈会溢出。

Longest Continuous Increasing Subsequence 2

note that, 题 Longest Increasing Continuous subsequence 的 follow up, 变成一道比较难的题了。从之前的一维 DP 变为现在的二维 DP，自增方向可从上下左右四个方向进行。需要结合 DFS 和动态规划两大重量级武器。 根据二维 DP 的通用方法，我们首先需要关注状态及状态转移方程，状态转移方程相对明显一点，即上下左右四个方向的元素值递增关系，根据此转移方程，**不难得到我们需要的状态为dp[i][j]——表示从坐标(i, j)出发所得到的最长连续递增子序列。**根据状态及转移方程我们不难得到初始化应该为1或者0，这要视具体情况而定。

这里我们可能会纠结的地方在于自增的方向，平时见到的二维 DP 自增方向都是从小到大，而这里的增长方向却不一定。**这里需要突破思维定势的地方在于我们可以不理会从哪个方向自增，只需要处理自增和边界条件即可。**根据转移方程可以知道使用递归来解决是比较好的方式，这里关键的地方就在于递归的终止条件。比较容易想到的一个递归终止条件自然是当前元素是整个矩阵中的最大元素，索引朝四个方向出发都无法自增，因此返回1. 另外可以预想到的是如果不进行记忆化存储，递归过程中自然会产生大量重复计算，根据记忆化存储的通用方法，这里可以以结果是否为0(初始化为0时)来进行区分。

public int longestContinuousIncreasingSubsequence2(int[][] matrix) {
    // write your code here
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;

    int max = 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dp[i][j] == 0) {
                max = Math.max(max, dfs(matrix, dp, i, j));
            }
        }
    }
    return max;
}

private int dfs(int[][] matrix, int[][] dp, int row, int col) {
    if (dp[row][col] != 0) return dp[row][col];  // check whether it has redundant calculation.

    int upper = 0, down = 0, left = 0, right = 0;
    // increasing from down to up
    if (row > 0 && matrix[row - 1][col] > matrix[row][col]) upper = dfs(matrix, dp, row - 1, col);
    if (row < matrix.length - 1 && matrix[row + 1][col] > matrix[row][col]) down = dfs(matrix, dp, row + 1, col);
    if (col > 0 && matrix[row][col - 1] > matrix[row][col]) left = dfs(matrix, dp, row, col - 1);
    if (col < matrix[0].length - 1 && matrix[row][col + 1] > matrix[row][col]) right = dfs(matrix, dp, row, col + 1);

    int temp1 = Math.max(upper, down);
    int temp2 = Math.max(left, right);

    dp[row][col] = Math.max(temp1, temp2) + 1;

    return dp[row][col];
}

or we can use array index offset to simplify the loop process.

private static int dfs(int[][] matrix, int[][] dp, int row, int col) {
    if (dp[row][col] != 0) return dp[row][col];

    int ans = 1;
    for (int[] pair : pairs) {
        int x = pair[0] + row;
        int y = pair[1] + col;

        if (x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length) {
            if (matrix[row][col] < matrix[x][y]) {
                ans = Math.max(dfs(matrix, dp, x, y) + 1, ans);
            }
        }
    }
    dp[row][col] = ans;
    return ans;
}

private static final int[][] pairs = {{0,1}, {0,-1}, {1,0}, {-1,0}};

Summary:

when to use memorization?

• 状态转移特别麻烦，不是顺序性
• 初始化状态不是很容易找到

shortcoming of memorization

• 耗费更多空间，无法使用滚动数组优化
• 递归深度肯能会很深

Word Break

brute force method is to use recursion and backtracking. For finding the solution, we check every possible prefix of that string in the dictionary of words, if it is found in the dictionary, then the recursive function is called for the remaining portion of that string. And, if in some function call it is found that the complete string is in dictionary, then it will return true.

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return word_Break(s, new HashSet(wordDict), 0);
    }
    public boolean word_Break(String s, Set<String> wordDict, int start) {
        if (start == s.length()) {
            return true;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end)) {
                return true;
            }
        }
        return false;
    }
}

use memorization, just Boolean[] memo to store the intermediate result.

time complexity is O(n^2) size of recursion tree can go up to n^2

space complexity is O(n) the depth of recursion tree can go up to n.

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return word_Break(s, new HashSet(wordDict), 0, new Boolean[s.length()]);
    }
    public boolean word_Break(String s, Set<String> wordDict, int start, Boolean[] memo) {
        // exit base case...
        if (start == s.length()) {
            return true;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, memo)) {
                return memo[start] = true;
            }
        }
        return memo[start] = false;
    }
}

Or we can use BFS to solve the problem.

...

Word break 2

first, we think about the Naive brute force method.

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        return dfs(s, set);
    }

    private ArrayList<String> dfs(String s, Set<String> set) {
        ArrayList<String> result = new ArrayList<>();
        int n = s.length();
        // base case
        if (n <= 0) return result;

        // recursive case
        for (int i = 1; i <= n; ++i) {
            String cur = s.substring(0, i);
            if (set.contains(cur)) {
                if (n == i) {
                    result.add(cur);
                } else {
                    String postfix = s.substring(i);
                    ArrayList<String> temp = dfs(postfix, set);
                    for (String str : temp) {
                        str = cur + " " + str;
                        result.add(str);
                    }
                }
            }
        }
        return result;
    }
}

But it will result in TLE.

So we think about memorization by using HashMap. What I mean by that, is to store the postfix String and List of String pair.

So we will get the following memorization solution based on the above one.

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        Map<String, ArrayList<String>> map = new HashMap<>();
        return dfs(s, set, map);
    }

    private ArrayList<String> dfs(String s, Set<String> set, Map<String, ArrayList<String>> map) {
        if (map.containsKey(s)) {
            return map.get(s);
        }

        ArrayList<String> result = new ArrayList<>();
        if (s.length() <= 0) return result;

        if (set.contains(s)) {
            result.add(s);
        }

        for (int i = 1; i < s.length(); ++i) {
            String cur = s.substring(0, i);
            if(!set.contains(cur)) {
                continue;
            }

            String suffix = s.substring(i);
            ArrayList<String> temp = dfs(suffix, set, map);

            for (String str : temp) {
                result.add(cur + " " + str);
            }
        }

        map.put(s, result);
        return result;
    }
}