题目描述

给你一个整数方阵 arr，定义非零偏移下降路径为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

请你返回非零偏移下降路径数字和的最小值。

样例

输入：arr = [[1,2,3],[4,5,6],[7,8,9]]
输出：13
解释：
所有非零偏移下降路径包括：
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ，所以答案是 13。

限制

• 1 <= arr.length == arr[i].length <= 200
• -99 <= arr[i][j] <= 99

算法1

(动态规划) $O(nm^2)$

1. 设 $f(i, j)$ 表示到达第 $i$ 行第 $j$ 列时的最小值。
2. 初始时 $f(0, j) = arr(0, j)$，其余为正无穷。
3. 转移时，枚举 $k$，当 $j \neq k$ 时，转移 $f(i, j) = \min(f(i, j), f(i - 1, k) + arr(i, j))$。
4. 最终答案为 $\min(f(n - 1, j))$。

时间复杂度

• 共有 $nm$ 个状态，每个状态有 $O(m)$ 种转移，故时间复杂度为 $O(nm^2)$。

空间复杂度

• 需要 $O(nm)$ 的空间存储状态。
• 可以利用滚动数组优化到 $O(m)$ 的空间。

C++ 代码

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& arr) {
        int n = arr.size(), m = arr[0].size();
        const int INF = 50000;
        vector<vector<int>> f(n, vector<int>(m, INF));
        for (int i = 0; i < m; i++)
            f[0][i] = arr[0][i];

        for (int i = 1; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < m; k++)
                    if (j != k)
                        f[i][j] = min(f[i][j], f[i - 1][k] + arr[i][j]);

        int ans = INF;

        for (int i = 0; i < m; i++)
            ans = min(ans, f[n - 1][i]);

        return ans;
    }
};

算法2

(动态规划优化) $O(nm)$

1. 在算法 1 的基础上优化，不再枚举 $O(m)$ 种转移。
2. 额外开两个数组 $l(i, j)$ 和 $r(i, j)$ 分别记录第 $i$ 行，从第 0 列到第 $j$ 列的最小值和从第 $m - 1$ 列到第 $j$ 列的最小值。
3. 这样每次转移就只需要 $f(i, j) = \min(l(i - 1, j - 1), r(i - 1, j + 1)) + arr(i, j)$。

时间复杂度

• 共有 $nm$ 个状态，每次转移只需要常数时间，故时间复杂度为 $O(nm)$。

空间复杂度

• 需要 $O(nm)$ 的空间存储状态。
• 可以利用滚动数组优化到 $O(m)$ 的空间。

C++ 代码

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& arr) {
        int n = arr.size(), m = arr[0].size();
        const int INF = 50000;
        vector<vector<int>> f(n, vector<int>(m, INF));
        vector<vector<int>> l(n, vector<int>(m, INF));
        vector<vector<int>> r(n, vector<int>(m, INF));

        for (int i = 0; i < m; i++)
            f[0][i] = arr[0][i];

        for (int i = 1; i < n; i++) {

            l[i - 1][0] = f[i - 1][0];
            for (int j = 1; j < m; j++)
                l[i - 1][j] = min(l[i - 1][j - 1], f[i - 1][j]);

            r[i - 1][m - 1] = f[i - 1][m - 1];
            for (int j = m - 2; j >= 0; j--)
                r[i - 1][j] = min(r[i - 1][j + 1], f[i - 1][j]);

            for (int j = 0; j < m; j++) {
                if (j > 0)
                    f[i][j] = min(f[i][j], l[i - 1][j - 1] + arr[i][j]);
                if (j < m - 1)
                    f[i][j] = min(f[i][j], r[i - 1][j + 1] + arr[i][j]);
            }
        }

        int ans = INF;

        for (int i = 0; i < m; i++)
            ans = min(ans, f[n - 1][i]);

        return ans;
    }
};