[LeetCode]64.Minimum Path Sum

【题目】

Given amxngrid filled with non-negative numbers, find a path from top left to bottom right whichminimizesthe sum of all numbers along its path.

Note:You can only move either down or right at any point in time.

【思路】

设sum[i][j] 到位置（i,j）时路径最小和

状态转移方程：

sum[i][j] = min(sum[i][j-1] ,sum[i-1][j]) + grid[i][j]

优化（空间轮转）：

sum[j] = min(sum[j],sum[j-1]) + grid[i][j]

【代码】

/*————————————* 日期：2015-02-04* 作者：SJF0115* 题目: 64.Minimum Path Sum* 网址：https://oj.leetcode.com/problems/minimum-path-sum/* 结果：AC* 来源：LeetCode* 博客：—————————————*/#include <iostream>#include <vector>#include <cstring>#include <algorithm>using namespace std;class Solution {public:int minPathSum(vector<vector<int> > &grid) {if(grid.empty()){return 0;}//ifint row = grid.size();int col = grid[0].size();vector<int> sum(grid[0]);// 第一行 只能从左边过来for(int i = 1;i < col;++i){sum[i] += sum[i-1];}//for// 动态规划// sum[j] = min(sum[j],sum[j-1]) + grid[i][j]for(int i = 1;i < row;++i){sum[0] += grid[i][0];for(int j = 1;j < col;++j){sum[j] = min(sum[j],sum[j-1]) + grid[i][j];}//for}//forreturn sum[col-1];}};int main(){Solution s;vector<vector<int> > grid = {{1,5,3,7},{2,6,4,1},{5,4,6,5}};int result = s.minPathSum(grid);// 输出cout<<result<<endl;return 0;}

，做事不怕难，自无难人事。