[LC] 62. Unique Paths

[seungriyou]

https://leetcode.com/problems/unique-paths/

Approach

Idea 1: 2D DP (Space O(n^2))

• dp[i][j] = i 번째 row, j 번째 column의 칸에 도달하는 unique path의 개수
• i == 0, j == 0 인 경우에는 0으로 padding을 두고, dp[1][1]는 1로 초기화한다.
• 단순하게 위의 row부터, 각 row에서는 왼쪽 column 부터 확인하며 윗 칸까지의 값(dp[i - 1][j])과 왼쪽 칸 까지의 값(dp[i][j - 1])을 더한다.

Idea 2: 1D DP (Space O(n))

• 2D DP에서, 하나의 row, 즉 바로 윗 row에 대해서만 tracking 하면 되므로 1D DP로 최적화할 수 있다.
• 1D DP 리스트를 계속해서 in-place로 더해가며 업데이트하면, 2D DP에서 윗 칸까지의 값(dp[i - 1][j])을 더했던 것과 같은 효과를 낸다.

Complexity

• Time: O(m * n)
• Space: (2D) O(m * n) / (1D) O(n)