题目链接

Leetcode.931 下降路径最小和 rating : 1573

题目描述

给你一个 n x n 的 方形 整数数组 $matrix$ ，请你找出并返回通过 $matrix$ 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 $(row,col)$ 的下一个元素应当是 $(row+1,col-1)$、$(row+1,col)$ 或者 $(row+1,col+1)$ 。

示例 1：

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：如图所示，为和最小的两条下降路径

示例 2：

输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：如图所示，为和最小的下降路径

提示

• $n=matrix.length=matrix[i].length$
• $1\le n\le 100$
• $-100\le matrix[i][j]\le 100$

解法一 ： 记忆化搜索

我们定义 $f(x,y)$ 为从 $(x,y)$ 到第一排的最小下降路径和。

位置 $(x,y)$ 可以移动到三个位置 $(x-1,y-1)$ ， $(x-1,y)$ ， $(x-1,y+1)$。

所以 f ( x , y ) = m i n { f ( x − 1 , y − 1 ) , f ( x − 1 , y ) , f ( x − 1 , y + 1 ) } + m a t r i x [ x ] [ y ] f(x,y) = min\{ f(x - 1,y - 1) , f(x - 1,y) , f(x - 1 , y + 1) \} + matrix[x][y] f(x,y)=min{f(x−1,y−1),f(x−1,y),f(x−1,y+1)}+matrix[x][y]

由于在递归的过程中可能多次访问同一个状态，所以我们用一个数组 $f$ 来记录所以已经遍历过的状态，再次遍历到直接返回即可。

当 $x=0$ 时，说明已经访问到了第一排，此时直接返回 $matrix[0][y]$ 即可。

当 $y<0||y\ge n$ 时，说明此时已经来到递归边界，由于我们求得时 最小 路径和，所以直接返回最大值 $INT\_MAX$ 即可。

时间复杂度： $O(n^2)$

C++代码：

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& g) {
        int n = g.size();
        int f[n][n];
        memset(f,0x3f,sizeof f);

        function<int(int,int)> dfs = [&](int x , int y) -> int{
            if(y < 0 || y >= n) return INT_MAX;
            if(x == 0) return g[x][y];

            if(f[x][y] != 0x3f3f3f3f) return f[x][y];

            int& ans = f[x][y];

            ans = min(dfs(x - 1 , y) , min(dfs(x - 1 , y - 1) , dfs(x - 1 , y + 1))) + g[x][y];

            return ans;
        };


        int ans = INT_MAX;

        for(int j = 0;j < n;j++){
            ans = min(ans , dfs(n - 1 , j));
        }

        return ans;
    }
};

解法二 ： 动态规划

我们只需要把记忆化搜索的代码翻译成动态规划的代码即可。

我们定义 $f[i][j]$ 为 从 $(i,j)$ 出发，到达第一排的最小路径和。

状态转移方程还是：

f [ i ] [ j ] = m i n { f [ i − 1 ] [ j − 1 ] , f [ i − 1 ] [ j ] , f [ i − 1 ] [ j + 1 ] } + m a t r i x [ i ] [ j ] f[i][j] = min\{f[i-1][j-1],f[i-1][j],f[i-1][j+1]\} + matrix[i][j] f[i][j]=min{f[i−1][j−1],f[i−1][j],f[i−1][j+1]}+matrix[i][j]

但是这样定义的话，没有能表示 递归边界 的状态，即 $j=-1$ 和 $j=n$ 的情况。

那么这样的话，我们干脆对于第二纬的状态，让其整体向右偏移两个单位。然后用 $f[i][j+1]$ 表示 从 $(i,j)$ 出发，到达第一排的最小路径和。这样的话，状态转移方程就变成：

f [ i ] [ j + 1 ] = m i n { f [ i − 1 ] [ j ] , f [ i − 1 ] [ j + 1 ] , f [ i − 1 ] [ j + 2 ] } + m a t r i x [ i ] [ j ] f[i][j+1] = min\{f[i-1][j],f[i-1][j+1],f[i-1][j+2]\} + matrix[i][j] f[i][j+1]=min{f[i−1][j],f[i−1][j+1],f[i−1][j+2]}+matrix[i][j]

这样我们就可以表示 递归边界 了，即用 $f[i][0]=\infty ,f[i][n+1]=\infty$，表示 $f[i][-1],f[i][n]$ 的状态。

初始时 $f[0][j+1]=matrix[0][j]$。

时间复杂度： $O(n^2)$

C++代码：

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& g) {
        int n = g.size();
        int f[n][n + 2];
        memset(f , 0x3f , sizeof f);

        for(int j = 0;j < n;j++){
            f[0][j + 1] = g[0][j];
        }

        for(int i = 1;i < n;i++){
            for(int j = 0;j < n;j++){
                f[i][j + 1] = min(f[i - 1][j] , min(f[i - 1][j + 1] , f[i - 1][j + 2])) + g[i][j];
            }
        }

        int ans = INT_MAX;
        for(int j = 1;j <= n + 1;j++) ans = min(ans , f[n - 1][j]);

        return ans;
    }
};