LC.P931[下降路径最小和]

方法一：DFS(超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    
    int[][] matrix;

    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length, ans = Integer.MAX_VALUE;
        this.matrix = matrix;
        for (int col = 0; col < n; ++col) {
            ans = Math.min(ans, dfs(n - 1, col));
        }
        return ans;
    }

    private int dfs(int row, int col) {
        if (col < 0 || col >= matrix.length) return Integer.MAX_VALUE; // 越界
        if (row == 0) return matrix[0][col]; // 到达第一行
        return Math.min(Math.min(dfs(row - 1, col - 1), dfs(row - 1, col)), dfs(row - 1, col + 1)) + matrix[row][col];
    }
}
  • 时间复杂度：$O(n3^n)$
  • 空间复杂度：$O(n)$

方法二：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {

    int[][] matrix;
    int[][] cache;

    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length, ans = Integer.MAX_VALUE;
        this.matrix = matrix;
        cache = new int[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(cache[i], Integer.MIN_VALUE);
        }

        for (int col = 0; col < n; ++col) {
            ans = Math.min(ans, dfs(n - 1, col));
        }
        return ans;
    }

    private int dfs(int row, int col) {
        if (col < 0 || col >= matrix.length) return Integer.MAX_VALUE; // 越界
        if (row == 0) return matrix[0][col]; // 到达第一行
        if (cache[row][col] != Integer.MIN_VALUE) return cache[row][col];
        return cache[row][col] = Math.min(Math.min(dfs(row - 1, col - 1), dfs(row - 1, col)), dfs(row - 1, col + 1)) + matrix[row][col];
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$

方法三：1:1翻译成递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] f = new int[n][n + 2]; // 防止 col = -1 || col = n 的越界情况
        System.arraycopy(matrix[0], 0, f[0], 1, n);
        for (int row = 1; row < n; ++row) {
            f[row - 1][0] = f[row - 1][n + 1] = Integer.MAX_VALUE;
            for (int col = 0; col < n; ++col) {
                f[row][col + 1] = Math.min(Math.min(f[row - 1][col], f[row - 1][col + 1]), f[row - 1][col + 2]) + matrix[row][col];
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int col = 1; col <= n; ++col) {
            ans = Math.min(ans, f[n - 1][col]);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$