64. Minimum Path Sum

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

Minimum Path Sum - LeetCode

 

cell별로 가중치가 존재하는 m x n 크기의 grid가 주어졌을 때, 우하단 cell까지 도착하는 경로 중 가중치의 합이 제일 적은 합을 반환하는 문제다.

 

일전에는 우하단 cell에 도달 하기까지의 유일한 경로 수를 반환하는 문제였지만, 가중치의 최소 합을 반환하면 되고, 풀이법은 크게 다르지 않다. (DP)

 

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        cache_ = vector<int>(grid[0].size(), 0);

        for (int i=0; i<grid.size(); ++i)
        {
            cache_[0] += grid[i][0];

            for (int j=1; j<grid[0].size(); ++j)
            {
                if (i && cache_[j] < cache_[j - 1])
                    cache_[j] += grid[i][j];
                else
                    cache_[j] = cache_[j - 1] + grid[i][j];
            }
        }
        
        return cache_[grid[0].size() - 1];
    }
private:
    vector<int> cache_;
};