[Dynamic Programming][Medium] 64. Minimum Path Sum

 

https://leetcode.com/problems/minimum-path-sum/description

 

Q. m x n의 grid가 주어질 때, 우하단에 도달하는 경로 중 최소 값을 구하라. 

 이때 우측과 하단으로 한칸씩만 이동할 수 있다. 

 

 

Solution 

 문제에 의해 특정 위치에서 우하단으로 가는 경로는

 우측 또는 하단으로 갈 수 있을 때, 

 f(최소우측경로) + f(최소하단경로) 가 된다. 

 우하단에 도달하면 그 위치 값만 반환하면 된다. 

 

로직으로 써 본다. 

 

    int minPS_dp(vector<vector<int>>& grid, int x, int y,  vector<int>& vCache)
    {
        int h = grid.size();
        int w = grid[0].size();

        if(x == w-1 && y == h-1)
            return grid[y][x];

        int idx = y * w + x;
        if(vCache[idx] >= 0)    return vCache[idx];
        
        int right = x<w-1 ? grid[y][x] + minPS_dp(grid, x+1, y, vCache) : INT_MAX;
        int down = y<h-1 ? grid[y][x] + minPS_dp(grid, x, y+1, vCache) : INT_MAX;
        vCache[idx] = min(right, down);
        return vCache[idx];
    }

public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        vector<int> vCache;
        vCache.resize(grid.size()*grid[0].size(), -1);
        return minPS_dp(grid, 0, 0, vCache);
    }

 

만족스럽진 않지만, 가독성있는 코드의 결과.