首页 > 代码库 > Leetcode:Minimum Path Sum 矩形网格最小路径和
Leetcode:Minimum Path Sum 矩形网格最小路径和
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.
解题分析：
每次只能向下或者向右走，其实就是说明了 搜索过程中的状态扩展情况
设 f[i,j]表示 从原点到 grid[i][j]的最小路径和，则有以下动态规划特征式：
f[i,j] = min { f[i-1][j], f[i][j-1] } + grid[i][j]
注意边界情况
class Solution {public: int minPathSum(vector<vector<int> > &grid) { int nRow = grid.size(); int nCol = 0; if (nRow == 0) { return 0; } else { nCol = grid.at(0).size(); } vector<vector<int>> path(nRow, vector<int>(nCol, 0)); for (int i = 0; i < nRow; ++i) { for (int j = 0; j < nCol; ++j) { if (i == 0 && j == 0) path.at(0).at(0) = grid.at(0).at(0); if (i == 0 && j != 0) path.at(i).at(j) = path.at(i).at(j-1) + grid.at(i).at(j); if (i != 0 && j == 0) path.at(i).at(j) = path.at(i-1).at(j) + grid.at(i).at(j); if (i != 0 && j != 0) path.at(i).at(j) = std::min(path.at(i-1).at(j), path.at(i).at(j-1)) + grid.at(i).at(j); } } return path.at(nRow-1).at(nCol-1); }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。