建材网站设计,延安网站建设电话,网站开发教程 模板,crm系统登录界面思路一#xff1a;dfs深度优先搜索#xff0c;然后取最小路径值#xff0c;但是时间消耗较大#xff0c;时间复杂度可能不满足#xff0c;代码如下#xff1a;
class Solution {
public:int res 1000000;int rows,cols;int minPathSum(vectorvectorint…
思路一dfs深度优先搜索然后取最小路径值但是时间消耗较大时间复杂度可能不满足代码如下
class Solution {
public:int res 1000000;int rows,cols;int minPathSum(vectorvectorint grid) {rows grid.size();cols grid[0].size();dfs(grid,0,0,0);return res;}void dfs(vectorvectorint grid,int row,int col,int sum){sum grid[row][col];if(row rows-1 col cols-1){res min(sum,res);return;}if(row rows-1) dfs(grid,row1,col,sum);if(col cols-1) dfs(grid,row,col1,sum);}
};
思路二动态规划记录每个节点的最小路径值最后可得出最后一个节点的最小路径值
class Solution {
public:int minPathSum(vectorvectorint grid) {int rows grid.size();int cols grid[0].size();vectorvectorint dp(rows,vectorint(cols));//第一个节点为本身值dp[0][0] grid[0][0];//第一行的最小路径值因为只有一条路径for(int i 1;i cols;i){dp[0][i] dp[0][i-1] grid[0][i];}//第一列的最小路径值因为只有一条路径for(int i 1;i rows;i){dp[i][0] dp[i-1][0] grid[i][0];}//其余的最小路径值for(int i 1;i rows;i){for(int j 1;j cols;j){//从左或者从右到达当前节点比较两者最小值然后加上自身dp[i][j] min(dp[i][j-1],dp[i-1][j]) grid[i][j];}}//得出最后一个节点的最小路径值return dp[rows-1][cols-1];}
};
