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

方法一：递归回溯 
// 超时  用例通过率：50.00%
#include <algorithm>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int dfs(vector<vector<int> >& matrix, int m, int n)
    {
        if(m==0 && n==0)
            return matrix[m][n];
        else if(m>0 && n==0)
            return dfs(matrix,m-1,n)+matrix[m][n];
        else if(m==0 && n>0)
            return dfs(matrix,m,n-1)+matrix[m][n];
        else
            return min(dfs(matrix,m-1,n),dfs(matrix,m,n-1)) + matrix[m][n];
    }

    int minPathSum(vector<vector<int> >& matrix) {
        // 递归回溯
        int m=matrix.size();
        int n=matrix[0].size();

        return dfs(matrix,m-1,n-1);  
    }
};


方法二：动态规划：

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        // 动态规划
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));

        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                if(i==0 && j==0)
                    dp[i][j] = matrix[i][j];
                else if(i==0 && j>0)
                    dp[i][j] = dp[i][j-1]+matrix[i][j];
                else if(i>0 && j==0)
                    dp[i][j] = dp[i-1][j]+matrix[i][j];
                else
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1])+matrix[i][j];
            }
        }

        return dp[m-1][n-1];
    }
};