23.03.27. 풀었던 문제들

Leetcode 64. Minimum Path Sum

 간단한 DP 문제. array의 top left부터 bottom right까지, [오른쪽으로 움직이거나, 아래로 움직이거나] 2개의 선택지로 도달하는 최소 weight를 얻어내는 방법이다. graph로 생각하면 top left부터 모든 vertex까지 dijkstra로 알아내야 하면 O(nlogn)이다. 그러나 이 문제의 경우 DP를 사용할 수 있다.

•  dp[r][c] = weight[r][c] + (dp[r-1][c], dp[r][c-1])

// Runtime 7 ms Beats 90.29%
// Memory 9.5 MB Beats 98.74%

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

        for(int c = 1; c<n; c++){
            grid[0][c] += grid[0][c-1];
        }
        for(int r = 1; r<m; r++){
            grid[r][0] += grid[r-1][0];
        }

        for(int r = 1; r<m; r++){
            for(int c = 1; c<n; c++){
                grid[r][c] += min(grid[r-1][c], grid[r][c-1]);
            }
        }

        return grid[m-1][n-1];
    }
};

 

시간복잡도

 DP 시 array의 모든 element를 한 번씩 탐색하므로 O(mn)

 

공간복잡도

 추가 공간을 사용하지 않는다. 문제 조건에서 m by n의 array를 사용하므로 O(mn)