[LeetCode] Unique Paths

문제

Share

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Right -> Down 2. Right -> Down -> Right 3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3 Output: 28

 

Approach

전형적인 DP 문제로 memo[i][j] = memo[i-1][j] + memo[i][j-1]임에 착안하여 푼다.

공간복잡도는 O(m*n)

 

Optimization

위 방법은 2차원배열로 메모를 하나 memo[i][j]를 채우기 위해서 알아야하는 칸은 이전 행의 한칸, 이전 열의 한칸 뿐이므로

2차원배열을 쓰지 않고도 DP를 할 수 있다.

이러면 공간복잡도가 O(n)이 되는데 실제 구현할때 위 방법은 그냥 정수형배열로 memo를하고

이 방법은 vector<int>로 memo를 해서 그런지 메모리 사용량은 위 방법이 더 적었다.

 

Code

2차원 배열: https://github.com/chi3236/algorithm/blob/master/LeetCode_UniquePaths.cpp

chi3236/algorithm

Optimized: https://github.com/chi3236/algorithm/blob/master/LeetCode_UniquePaths_optimized.cpp