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

两种方法解决最小路径和的问题，一种方法是递归（超时），另一种方法是动态规划。其实动态规划和递归原理一样，都是将大问题转化为小问题求解的方法。本题的大小问题关系是：到nums[i][j]的最小路径和等于min(到上方nums[i-1][j]的最小和，到左方nums[i][j-1]的最小和） + nums[i][j]。

一、递归方法

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        // 用动态规划的方法实现最小路径和的问题
        // 原问题：求nums[0][0]到nums[i][j]的最小路径和， 该问题等于nums[i - 1][j]和nums[i][j - 1]的路径和的较小值+nums[i][j]
        // 子问题就是求nums[i-1][j]和nums[i][j-1]的最小路径和
        // 先尝试递归（自顶向下），再尝试动态规划（制表法，自底向上）
        return dfs(matrix, matrix.size() - 1, matrix[0].size() - 1);

    }

private:
    // 有别的参数需要传递，所以需要重新写递归函数
    int dfs (vector<vector<int>>& matrix, int i, int j) {
        // i和j分别为矩阵的行坐标和列坐标
        if (i == 0 && j == 0) return matrix[0][0];
        // 说明nums[i][j]在第一行，则其路径只有一种：从nums[0][0]向右而来，则其路径和
        else if (i == 0 && j != 0) return dfs(matrix, i, j-1) + matrix[i][j];
        else if (i != 0 && j == 0) return dfs(matrix, i-1, j) + matrix[i][j];

        else {
            return min(dfs(matrix, i-1, j), dfs(matrix, i, j-1)) + matrix[i][j];  // 到左边元素的最小路径和右边最小路径的较小值+当前值
        }
    }
};

二、动态规划方法

class Solution {
public:
    int minPathSum(vector<vector<int>>& matrix) {
        // 将递归转化为动态规划来做
        // 自底向上计算最小路径，这样可以避免递归的众多重复计算
        int nr = matrix.size();
        if (!nr) return 0;
        int nc = matrix[0].size();

        vector<vector<int>> dp(nr, vector<int>(nc));  // nr * nc的数组

        dp[0][0] = matrix[0][0];
        // 初始化行和列
        for (int i = 1; i < nr; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        } 

        for (int i = 1; i < nc; i++) {
            dp[0][i] = dp[0][i - 1] + matrix[0][i]; 
        }

        // 一行一行地填充动规数组
        for (int i = 1; i < nr; i++) {
            for (int j = 1; j < nc; j++) {
                // 对第i行
                dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + matrix[i][j];
            }
        }

        return dp[nr - 1][nc - 1];
    }
};