[LeetCode] 64. Minimum Path Sum

LeetCode - 64. Minimum Path Sum 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/minimum-path-sum/

풀이

2차원 정수형 벡터의 (0, 0)위치에서 시작했을 때 (R-1, C-1)에 도달하는데 필요한 최소 비용을 구하는 문제이다. 이때 오른쪽 또는 아래쪽으로만 이동할 수 있는 조건을 갖고 있다.

임의의 위치 (i, j)에 도달하는데 소요되는 최솟값은 (i, j)에 도달하기 이전의 위쪽/왼쪽 방향으로 이동하는데 소요되는 비용에 (i ,j) 칸의 비용을 더하면 된다.

따라서 미리 (0, j) 위치와 (i, 0) 위치에 대해서 누적값을 구해두고 아래의 코드를 통해 구할 수 있다.

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

소스 코드

class Solution {
    int mem[200][200];
public:
    int minPathSum(vector<vector<int>>& grid) {
        const int R = grid.size();
        const int C = grid[0].size();
        
        mem[0][0]= grid[0][0];
        
        for (int i = 1; i < R; ++i) {
            mem[i][0] = mem[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < C; ++i) {
            mem[0][i] = mem[0][i - 1] + grid[0][i];
        }
        
        for (int i = 1; i < R; ++i) {
            for (int j = 1; j < C; ++j) {
                mem[i][j] = min(mem[i - 1][j] + grid[i][j], mem[i][j - 1] + grid[i][j]);
            }
        }
        
        return mem[R - 1][C - 1];
    }
};