C++ ] leetCode 64 - 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.

 

Example 1:

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

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

 

 

 

 

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {

        int m = grid.size();
        int n = grid[0].size();

        for(int i = 1; i < m ; i++)
        {
            grid[i][0] += grid[i-1][0];    
        }

        for(int j =1 ; j < n ; j++)
        {
            grid[0][j] += grid[0][j-1];
        }

        for(int i = 1; i < m ; i++)
        {
            for(int j =1 ; j < n ; j++)
            {
                grid[i][j] += min(grid[i][j-1], grid[i-1][j]);
            }            
        }

        return grid[m-1][n-1];

    }
};

 

포인트는 경로를 알 필요가 없고, 최소합만 구하면 된다는 것이다.

 

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

 

최종목적지인 우하단 입장에서 보면 자신의 칸에 올 수 있는건 자신의 좌측칸 또는 상단칸이다. 그리고 이건 다른 모든칸도 마찬가지이다. grid[1~m-1][0]이랑 grid[0][1~n-1]만 제외하고.

 

일단 grid[0][0]은 출발점이고, grid[1~m-1][0]은 자신의 상단칸에서만 올 수 있고, grid[0][1~n-1] 자신의 좌측칸에서만 올 수 있다.

 

이점을 고려해서 누적합을 구하고, 다른칸들은 좌측칸/상단칸중에 minimum값을 누적한다.

 

마지막으로 목적지까지 도달하는 최소 합을 리턴한다.