首页 > 代码库 > [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问题,如果用grid保存路径和的话
很明显grid[i][j] = grid[i][j] + min(grid[i - 1][j], grid[i][j - 1]);
int minPathSum2(vector<vector<int>>& grid) { if (grid.empty())return 0; int row = grid.size(); int col = grid[0].size(); //其实可以不必申请空间 直接使用grid就行 for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (i==0 && j!=0) { grid[i][j] += grid[i][j - 1]; } if (i != 0 && j == 0) { grid[i][j] += grid[i - 1][j]; } if (i!=0&&j!=0) { grid[i][j] = grid[i][j] + min(grid[i - 1][j], grid[i][j - 1]); } } } return grid[row - 1][col - 1]; }
[leetcode-64-Minimum Path Sum]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。