首页 > 代码库 > leetcode 64. Minimum Path Sum
leetcode 64. Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
采用动态规划的方法,dp[i][j] = min(dp[i-1][j],dp[i],[j-1])+a[i][j];
1 class Solution { 2 public: 3 int minPathSum(vector<vector<int>>& grid) { 4 int m = grid.size(); 5 int n = grid[0].size(); 6 vector<vector<int> > dp(m,vector<int>(n)); 7 for(int i = 0;i < m;i++){ 8 for(int j = 0;j < n ;j++){ 9 if(i == 0){ 10 if(j == 0){//初始化 11 dp[i][j] = grid[i][j]; 12 } 13 else{//i==0 && j!=0 14 dp[i][j] = dp[i][j-1]+grid[i][j]; 15 } 16 } 17 else if(j == 0){//i!=0&& j==0 18 dp[i][j] = dp[i-1][j] + grid[i][j]; 19 } 20 else{//i,j!=0 21 dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]; 22 } 23 24 } 25 } 26 return dp[m-1][n-1]; 27 } 28 };
leetcode 64. Minimum Path Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。