二维/矩阵类DP

矩阵类的题目能用DFS解答的都要想到memoization来优化，Tree则不能用memo优化

Maximal Square

• 典型的矩阵类DP

• 求最大的都包含1的matrix并返回面积

• dp[i][j] means edge length of maximal square ending with matrix[i][j] as bottom-right corner

• if matrix[i][j] == 1, state: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

class Solution {
    /*
    dp[i][j] means edge length of maximal square ending with matrix[i][j] as bottom-right corner
    if matrix[i][j] == 1 && matrix[i - 1][j] == 1 && matrix[i][j - 1] == 1, dp[i][j] = dp[i - 1][j - 1] + 1
    state: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
    res:
    res = max(res, dp[i][j] * dp[i][j])
    */
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        int res = 0;
        //initialization
        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                res = 1;
            }
        }
        for (int j = 0; j < cols; j++) {
            if (matrix[0][j] == '1') {
                dp[0][j] = 1;
                res = 1;
            }
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    res = Math.max(res, dp[i][j] * dp[i][j]);
                }
            }
        }
        return res;
    }
}

Count Square Submatrices with All Ones

• maximal Square的升级版, 用的是同样的dp[i][j]的定义

• dp[i][j] means edge length of maximal square ending with matrix[i][j] as bottom-right corner

• 这里有个小trick， dp[i][j] also means number of squares with matrix[i][j] as bottom-right corner

• 所以最后cnt = sum(dp[i][j])

class Solution {
    /*
    dp[i][j] means edge length of largest square with matrix[i][j] as bottom-right corner
    dp[i][j] also means number of squares with matrix[i][j] as bottom-right corner
    if matrix[i][j] == 1, state: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
    res:
    cnt = sum(dp[i][j])
    */
    public int countSquares(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        int res = 0;
        //initialization
        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == 1) {
                dp[i][0] = 1;
                res += dp[i][0];
            }
        }
        for (int j = 0; j < cols; j++) {
            if (matrix[0][j] == 1) {
                dp[0][j] = 1;
                res += dp[0][j];
            }
        }
        if (matrix[0][0] == 1) res--;
        //state
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == 1) {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    res += dp[i][j];
                }
            }
        }
        return res;
    }
}

Triangle

• 二维matrix DP的入门题

• 正常思维应该是首先想到DFS解法，traverse 或者D&C

• 然后分析DFS的时间复杂度，发现是指数级，并且画一下过程图，发现可以用memo优化成多项式级别

• 非常经典的题目来比较DFS, DFS with memo, DP的不同思路

• DFS with memo是top-dwon, O(n^2) space

• 可以用bottom-up DP来优化成O(n) space

class Solution {
    /*
    nums[x,y]
    nums[x+1, y], nums[x + 1, y + 1]
    可以看成矩阵类问题
    traverse the matrix 
    D&C: Time: O(2^n)
    D&C with memo Time: O(n^2), Space: O(n^2)
    DP: bottom-up, O(n) space
    */
    public int minimumTotal(List<List<Integer>> triangle) {
        //return minPathSum(triangle, 0, 0, new HashMap<>());
        return dp(triangle);
    }
    //traverse
    int min = Integer.MAX_VALUE;
    private void traverse(List<List<Integer>> triangle, int x, int y, int pathSum) {
        if (x == triangle.size()) {
            min = Math.min(min, pathSum);
            return;
        }
        traverse(triangle, x + 1, y, triangle.get(x).get(y) + pathSum);
        traverse(triangle, x + 1, y + 1, triangle.get(x).get(y) + pathSum);
    }
    
    //divide & conquer
    private int minPathSum(List<List<Integer>> triangle, int x, int y) {
        if (x == triangle.size()) {
            return 0;
        }
        int left = minPathSum(triangle, x + 1, y);
        int right = minPathSum(triangle, x + 1, y + 1);
        int pathSum = Math.min(left, right) + triangle.get(x).get(y);
        return pathSum;
    }
    
    //divide & conquer with memo
    //Time: O(n^2)
    //Space: O(n^2)
    private int minPathSum(List<List<Integer>> triangle, int x, int y, Map<Integer, Integer> memo) {
        if (x == triangle.size()) {
            return 0;
        }
        //fetch from memo
        int key = x * triangle.size() + y;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        int left = minPathSum(triangle, x + 1, y, memo);
        int right = minPathSum(triangle, x + 1, y + 1, memo);
        int pathSum = Math.min(left, right) + triangle.get(x).get(y);
        memo.put(key, pathSum);
        return pathSum;
    }
    
    //bottom-up DP solutin, O(n) space
    //minSum[j] -> min(minSum[j], minSum[j + 1]) + triangle[i][j]
    //initialize for loop last row of triangle: minSum[j] == triangle[n - 1][j]
    //dp from second-to-last row, bottom up
    //return minSum[0]
    private int dp(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0 || triangle.get(0).size() == 0) return 0;
        int n = triangle.size();
        int[] minSum = new int[n];
        for (int j = 0; j < n; j++) {
            minSum[j] = triangle.get(n - 1).get(j);
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i ; j++) {
                minSum[j] = Math.min(minSum[j], minSum[j + 1]) + triangle.get(i).get(j);
            }
        }
        return minSum[0];
    }
}

Minimum Path Sum

• 最简单的二维坐标DP

• 可以用滚动数组优化空间成O(min(n, m))

class Solution {
    /*
    brute force, DFS-> combination problem-> O(2^N)
    有方向性-> DP to improve
    m*n matrix problem, so need O(m*n) extra space
    
    state: f[i][j] means min path sum from grid[0][0] to grid[i][j]
    
    function: f[i][j] = min(f[i - 1][j], f[i][j -1]) + grid[i][j]
    
    result: return f[m - 1][n - 1]
    
    initial:
    f[0][0] = grid[0][0]
    f[0][j] = f[0][j - 1] + grid[0][j]
    f[i][0] = f[i - 1][0] + grid[i][0]
    
    bonus: rolling array to make space improvement
    */
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length, n = grid[0].length;
        int[][] minSum = new int[m][n];
        //intialize
        minSum[0][0] = grid[0][0];
        for (int i = 1; i < m ; i++) {
            minSum[i][0] = minSum[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            minSum[0][j] = minSum[0][j - 1] + grid[0][j];
        }
        //state
        for (int i = 1; i< m ; i++) {
            for (int j = 1; j < n; j++) {
                minSum[i][j] = Math.min(minSum[i - 1][j], minSum[i][j - 1]) + grid[i][j];
            }
        }
        //result
        return minSum[m - 1][n - 1];
    }
    
    private int minPathSumWithRollingArray(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length, n = grid[0].length;
        int[][] minSum = new int[2][n];
        //intialize
        minSum[0][0] = grid[0][0];
        //state
        for (int i = 0; i< m ; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                if (i == 0) {
                    minSum[i % 2][j] = minSum[i % 2][j - 1] + grid[i][j];
                    continue;
                }
                if (j == 0) {
                    minSum[i % 2][j] = minSum[(i - 1) % 2][j] + grid[i][j];
                    continue;
                }
                minSum[i % 2][j] = Math.min(minSum[(i - 1) % 2][j], minSum[i % 2][j - 1]) + grid[i][j];
            }
        }
        //result
        return minSum[(m - 1) % 2][n - 1];
    }
}