方法一:递归回溯 // 超时 用例通过率: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]; } };