NC59 矩阵的最小路径和

题目描述：

给定一个 $n\ast mn\; *\; m$n∗m 的矩阵 $aa$a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

1. 深搜做法（TLE)

从左上角开始，每次向下或向右走，遍历所有路径，走到右下角时判断当前路径是不是最小的，如果是则更新之。

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int n, m;
    
    int dfs(int i, int j, vector<vector<int> >& matrix, int cur = 0) {
        if (i == n-1 && j == m-1) {
            return cur;
        } else {
            cur += matrix[i][j];
            if (i == n-1) {
                return dfs(i, j+1, matrix, cur); // 只能往下走
            } else if (j == m-1) {
                return dfs(i+1, j, matrix, cur); // 只能往右走
            } else {
                // 都能走，取最小的
                return min(dfs(i, j+1, matrix, cur), dfs(i+1, j, matrix, cur));
            }
           
        }
        
    }
    int minPathSum(vector<vector<int> >& matrix) {
        n = matrix.size(), m = matrix[0].size();
        
        
        return dfs(0, 0, matrix, 0);
    }
};

• 时间复杂度：$O\left(C_{n+m}^n\right)O(C\_\{n+m\}^n)$O(Cn+mn​), 因为遍历了每条路径，一共有$n+mn+m$n+m步，选$nn$n步向下，每种方案都搜索过了。
• 空间复杂度：$O(n+m)O(n+m)$O(n+m)，递归的最大深度是从左上角搜到右下角，共调用了n+m次。

2. 动态规划+空间优化

思路一之所以超时，是因为有大量重复的中间值被计算过，但是中间的路径对最终右下角的最优解是无关的， 这体现了动态规划算法的无后效性，因此本题可以考虑动态规划求解。

动态规划有4大要素：

• 状态的定义：定义$dp\left[i\right]\left[j\right]dp[i][j]$dp[i][j]表示从左上角走到点$(i,j)(i,j)$(i,j)的最优解
• 转移方程：因为$dp\left[i\right]\left[j\right]dp[i][j]$dp[i][j]只跟它左和上的点有关系，且取前面两点的最优方案即可，因此$dp\left[i\right]\left[j\right]=min\left(dp\right[i-1\left]\right[j],dp[i\left]\right[j-1\left]\right)+matrix\left[i\right]\left[j\right]dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j]$dp[i][j]=min(dp[i−1][j],dp[i][j−1])+matrix[i][j].
• 初始值：因为是求min，全初始化为最大值。
• 答案：$dp[n-1][m-1]dp[n-1][m-1]$dp[n−1][m−1], 其中n和m分别为行列。

用一张图分析上述过程：

如上图所示, 从起点走到红色的$(i,j)(i,j)$(i,j)点只有两种情况，分别是从黄色点向右走，或从绿色点向下走。因此要想以最优方案走到红色点，只需以最优方案走到黄色和绿色点，再判断黄色点和绿色点谁更优，即可。依次递推，可以得到走到终点的最优方案。

正常来说，要开辟$O\left(mn\right)O(mn)$O(mn)的dp数组，但是题目要求空间为$O\left(1\right)O(1)$O(1), 那么可以思考一下，如何优化。

我们发现如果压缩dp数组，是不能实现$O\left(1\right)O(1)$O(1)的，至多压缩掉一维。我们只能利用已有的空间了。当我们遍历到$(i,j)(i,j)$(i,j)点的时候，其实它的左上部分已经没有用了，我们只关注任意一点的最优解就行，因此可以在matrix数组上就地操作。

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(i == 0 && j == 0) continue;
                else if(i == 0)  matrix[i][j] = matrix[i][j - 1] + matrix[i][j];
                else if(j == 0)  matrix[i][j] = matrix[i - 1][j] + matrix[i][j];
                else matrix[i][j] = min(matrix[i - 1][j], matrix[i][j - 1]) + matrix[i][j];
            }
        }
        return matrix[n-1][m-1];

    }
};

• 时间复杂度：$O\left(mn\right)O(mn)$O(mn), 2重循环.
• 空间复杂度：$O\left(1\right)O(1)$O(1)，没有使用额外空间。