LeetCode 64: Minimum Path Sum

发布时间:2016-12-8 8:16:23 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode 64: Minimum Path Sum",主要涉及到LeetCode 64: Minimum Path Sum方面的内容,对于LeetCode 64: Minimum Path Sum感兴趣的同学可以参考一下。

Difficulty: 3 Frequency: 3 Problem: 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. Solution: class Solution { public: int minPathSum(vector<vector<int> > &grid) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<vector<int> >pathSumMatrix(grid); for (int i = 0; i<grid.size(); i++) { for (int j = 0; j<grid[i].size(); j++) { pathSumMatrix[i][j] = -1; } } pathSumMatrix[0][0] = grid[0][0]; return minPathSumRecursive(grid, pathSumMatrix, grid.size() - 1, grid[0].size() - 1); } int minPathSumRecursive(vector<vector<int> > &grid, vector<vector<int> > &pathSumMatrix, int i_row, int i_col) { if (pathSumMatrix[i_row][i_col]!=-1) return pathSumMatrix[i_row][i_col]; int i_up = i_row==0?0x7FFFFFFF:minPathSumRecursive(grid, pathSumMatrix, i_row - 1, i_col); int i_left = i_col==0?0x7FFFFFFF:minPathSumRecursive(grid, pathSumMatrix, i_row, i_col - 1); return pathSumMatrix[i_row][i_col] = (i_up<i_left?i_up:i_left) + grid[i_row][i_col]; } }; Notes: No comment. Haha.

上一篇:CSS Colors
下一篇:Lr参数和变量(一)

相关文章

相关评论