931. Minimum Falling Path Sum

DFS + memo

T: O(3^row)

S: O(row*col)

public class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;        
        Integer[][] memo = new Integer[m][n];
        
        int min = Integer.MAX_VALUE;
        // 從 row 0 開始跑所有 row 0 的 cell, 來做之後的分支
        // 所以把 0,0  0,1  0,2 丟入 dfs function
        for (int c = 0; c < n; c++) { // row 0, put all (row, col)
            // 因為有做 memo, 所以 0,1  0,2 跑的時候, 其實下面 dfs 的分支都計算過了
            min = Math.min(min, dfs(matrix, 0, c, memo));
        }
        return min;
    }
    // dfs function 來 recursive 計算 min path value
    private int dfs(int[][] matrix, int row, int col, Integer[][] memo) {
        int m = matrix.length;
        int n = matrix[0].length;
        if (!isValid(m, n, row, col)) {
            return 0;
        }
        if (memo[row][col] != null) {
            return memo[row][col];
        }

        int min = Integer.MAX_VALUE;
        
        for (int i = -1; i <= 1; i++) {
            if (!isValid(m, n, row, col+i)) { // why check row..., not row+1 ?
                // because row+1 check is in the beginning of dfs? so why need check?
                continue;
            }
            // for every cell (row, col) 
            // => has 3 branch => (row+1, col-1),(row+1, col), (row+1, col-1)
            // sum = 目前值 + 3 分支的值
            int sum = matrix[row][col] + dfs(matrix, row+1, col + i, memo);
            min = Math.min(min, sum); // 取最小的
            
        }
        memo[row][col] = min; // 紀錄最小值
        return min;
    }
    private boolean isValid(int m, int n, int row, int col) {
        return row >= 0 && row < m && col >=0 && col < n;
    }
}

/*

row.  [0,0  0,1  0,2]  
      /|\
r+1,c-1 c c+1 


T: O(3^row)
S: O(mn)

*/

DP

top down, because this Q ask from top to end's min path sum

T: O(mn)
S: O(mn)

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        int[][] dp = new int[m][n];
        for (int j = 0; j < n; j++) {
            dp[0][j] = matrix[0][j];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                
                dp[i][j] = dp[i-1][j];
                if (j-1 >= 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][j-1]);
                }
                if (j+1 < n) {
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][j+1]);
                }
                dp[i][j] += matrix[i][j];
            }
        }
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            res = Math.min(res, dp[m-1][j]);
        }
        return res;
    }
}

/*
so from questions:

dp[i][j]: the minimum sum of any falling path through matrix, from 0 to m-1 rows.

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + A[i][j]

at last row find the min(dp[m-1][j]), is the ans

T: O(mn)
S: O(mn)
*/