03/23/27. 문제 해결됨

Leetcode 64. 최소 경로 합계

간단한 DP 문제. 배열의 왼쪽 상단에서 오른쪽 하단으로 두 가지 옵션(오른쪽으로 이동 또는 아래로 이동)으로 달성할 수 있는 최소 가중치를 얻는 방법입니다. 그래프로 생각하면 왼쪽 상단부터 dijkstra를 사용하여 모든 노드를 파악해야 한다면 O(nlogn)입니다. 그러나이 문제에 대해 DP를 사용할 수 있습니다.

• dp(r)(c) = 가중치(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);
    }
};

시간적 복잡성

O(mn) 배열의 모든 요소가 DP 동안 한 번 검색되기 때문입니다.

공간적 복잡성

여분의 공간을 사용하지 않습니다. 문제 조건이 m x n 배열을 사용하기 때문에 O(mn)