NC59 矩阵的最小路径和

题目描述：

给定一个 $n * m$ 的矩阵 $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(C_{n+m}^n)$ , 因为遍历了每条路径，一共有 $n + m$ 步，选 $n$ 步向下，每种方案都搜索过了。
空间复杂度： $O (n + m)$ ，递归的最大深度是从左上角搜到右下角，共调用了n+m次。

2. 动态规划+空间优化

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

动态规划有4大要素：

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

用一张图分析上述过程：

alt

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

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

我们发现如果压缩dp数组，是不能实现 $O (1)$ 的，至多压缩掉一维。我们只能利用已有的空间了。当我们遍历到 $(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 (m n)$ , 2重循环.
空间复杂度： $O (1)$ ，没有使用额外空间。

题解 | #矩阵的最小路径和#

NC59 矩阵的最小路径和

题目描述：

1. 深搜做法（TLE)

2. 动态规划+空间优化