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.

풀이

230921 재 풀이
이전에는 (0,0) 좌표에서 시작했지만, 이 문제는 (m, n)부터 시작해서 (0,0)쪽으로 재귀적으로 푸는게 더 풀이가 심플하고 이해하기 쉬운것같다.

재귀 + memoization

class Solution {
public:
    int vis[201][201] = {0};
    int minsum(vector<vector<int>>& grid, int i , int j) {
        if (i < 0 || j < 0)
            return INT_MAX;
        if (i == 0 && j == 0)
            return grid[i][j];
        if (vis[i][j])
            return vis[i][j];
        
        vis[i][j] = grid[i][j] + std::min(minsum(grid, i - 1, j), minsum(grid, i, j - 1));
        return vis[i][j];
    }
    int minPathSum(vector<vector<int>>& grid) {
        return minsum(grid, grid.size() - 1, grid[0].size() - 1);
    }
};

풀이

230916 재 풀이
(0,0)부터 시작해서 (m, n)까지 재귀적반복 방법

기본 재귀구조 ->. TLE

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        return minsum(grid, 0, 0);
    }
    
    int minsum(vector<vector<int>>& grid, int i, int j) {
        if (i == grid.size() || j == grid[0].size())
            return INT_MAX;
        if (i == grid.size() - 1 && j == grid[0].size() - 1)
            return grid[i][j];
        
        return grid[i][j] + min(minsum(grid, i+1, j), minsum(grid, i, j+1));
    }
};

memoiazation

class Solution {
public:
    vector<vector<int>> mem;
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        mem = vector(row + 1, vector<int>(col + 1, -1));
        return minsum(grid, 0, 0);
    }
    
    int minsum(vector<vector<int>>& grid, int i, int j) {
        if (mem[i][j] != -1)
            return mem[i][j];
        if (i == grid.size() || j == grid[0].size())
            return INT_MAX;
        if (i == grid.size() - 1 && j == grid[0].size() - 1)
            return grid[i][j];
        
        mem[i][j] = grid[i][j] + min(minsum(grid, i+1, j), minsum(grid, i, j+1));
        return mem[i][j];
    }
};

해결

예전에 풀었던 안좋은 풀이법

#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);
}