> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/931.-minimum-falling-path-sum.md).

# 931. Minimum Falling Path Sum

## DFS + memo

T: O(3^row)

S: O(row\*col)

```java
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)
```

```java
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)
*/
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/931.-minimum-falling-path-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.