DFS+Memo

139. Word Break

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    Map<String, Boolean> memo = new HashMap<>();
    return dfs(s, dict, memo);
}

private boolean dfs(String s, Set<String> dict, Map<String, Boolean> memo) {
    if (dict.contains(s)) {
        return true;
    }
    if (memo.containsKey(s)) {
        return memo.get(s);
    }
    for (int i = 0; i < s.length(); i++) {
        String substring = s.substring(0, i);
        if (dict.contains(substring) && dfs(s.substring(i), dict, memo)) {
            memo.put(s, true);
            return true;
        }
    }
    memo.put(s, false);
    return false;
}

329. Longest Increasing Path in a Matrix

int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int[][] memo;
int res = 1;
public int longestIncreasingPath(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
    int m = matrix.length, n = matrix[0].length;
    memo = new int[m][n];
    for (int[] row : memo) Arrays.fill(row, -1);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            dfs(i, j, matrix, memo);
        }
    }
    return res;
}

private int dfs(int x, int y, int[][] matrix, int[][] memo) {
    int len = 1;
    for (int[] d : dir) {
        int nx = x + d[0], ny = y + d[1];
        if (inbound(matrix, nx, ny) && matrix[nx][ny] > matrix[x][y]) {
            if (memo[nx][ny] != -1) {
                len = Math.max(len, 1 + memo[nx][ny]);
            } else {
                len = Math.max(len, 1 + dfs(nx, ny, matrix, memo));
            }
        }
    }
    memo[x][y] = len;
    res = Math.max(res, memo[x][y]);
    return len;
}

private boolean inbound(int[][] m, int x, int y) {
    return x >= 0 && y >= 0 && x < m.length && y < m[0].length;
}