[leetcode] 64. Minimum Path Sum

[leetcode] 64. Minimum Path Sum

Description

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.

Example:

Input:[ [1,3,1], [1,5,1], [4,2,1]]Output: 7Explanation: Because the path 1→3→1→1→1 minimizes the sum.

分析

题目的意思是：给你一个矩阵，求找一条左上角到右下角的路径，使得路径上的值的和最小。

直接动态规划了，这里我没有用额外的dp数组，因为站在当前位置只有两种走法，一个是向右，一个是向下。即grid[i][j]=min(grid[i][j-1],grid[i-1][j])+grid[i][j];另外考虑i=0的情况，j=0的情况和两者都为0的情况就行了。

代码

class Solution {public: int minPathSum(vector>& grid) { int m=grid.size(); int n=grid[0].size(); for(int i=0;i

参考文献

​​64. Minimum Path Sum​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。