64. Minimum Path Sum

发表于 | 分类于

每日一题 2019 - 04 - 07

题目：

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:

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

解法：

这个让我们求出从地图左上角到右下角的最短路径，最简单的方法就是动态规划的思想，使用 now[width+1][length+1] 记录下走到当前路径下的最大代价，找出递推关系:

1
2
3
4
5
6
7
8
if( now[i-1][j]  >= now[i][j-1] )
{
    now[i][j] = now[i][j-1] + grid[i-1][j-1] ;
}
else
{
    now[i][j] = now[i-1][j] + grid[i-1][j-1] ;
}

即可完成题解

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int length = grid[0].size() ;
        int width = grid.size();
        int now[width+1][length+1] = {0} ;
        for(int i = 0 ; i <= width ; i ++)
        {
            now[i][0] = INT_MAX ;
        }
        for(int i = 0 ; i <= length  ; i ++)
        {
            now[0][i] = INT_MAX ;
        }
        now[1][1] = grid[0][0] ;
        for(int i = 1 ; i <= width ; i ++ )
        {
            for(int j = 1 ; j <= length ; j ++)
            {
                if( i == 1 && j == 1)
                {
                    continue ;
                }
                if( now[i-1][j]  >= now[i][j-1] )
                {
                    now[i][j] = now[i][j-1] + grid[i-1][j-1] ;
                }
                else
                {
                    now[i][j] = now[i-1][j] + grid[i-1][j-1] ;
                }
            }
        }
        return now[width][length];
    }
};
0%
undefined