Leetcode - 64. Minimum Path Sum

문제

2차원 배열이 주어지고 좌상단에서 우하단으로 이동할때 가능한 경로중 최소비용은? (이동시 경로의 값을 더함)

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.

해결

dp문제

#define min(a,b)    (((a) < (b)) ? (a) : (b))
int mem[201][201];
int path_sum(int **grid, int row, int col) {
    if (row < 0)
        return -1;
    if (col < 0)
        return -1;
    if (mem[row][col])
        return mem[row][col];
    
    int a = path_sum(grid, row - 1, col);
    int b = path_sum(grid, row, col - 1);
    if (a == -1 && b == -1) {
        return grid[row][col];
    } else if (b == -1) {
        return a + grid[row][col];
    } else if (a == -1) {
        return b + grid[row][col];
    }
    
    mem[row][col] = min(a, b) + grid[row][col];
    return mem[row][col];
}

int minPathSum(int** grid, int gridSize, int* gridColSize){
    memset(mem, 0, sizeof(int) * 201 * 201);
    return path_sum(grid, gridSize - 1, *gridColSize - 1);
}