문제
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? Leetcode
코드
int uniquePaths(int m, int n) {
vector<vector<long long>> v(n, vector<long long>(m, -1));
if (m == 0 && n == 0) return 0;
if (m == 1 && n == 1) return 1;
v[0][0] = 0;
if (m != 1) v[0][1] = 1;
if (n != 1) v[1][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (v[i][j] == -1) {
long long val = 0;
if (i - 1 >= 0) val += v[i - 1][j];
if (j - 1 >= 0) val += v[i][j - 1];
v[i][j] = val;
}
}
}
return v[n - 1][m - 1];
}
풀이
현재값 = 왼쪽에서 오는 값(v[i][j - 1]) + 위에서 오는 값(v[i - 1][j])
메모리를 줄일 수 있는 방법
- 결국 필요한 건 이전 row와 현재 row임
int pre[n - 1], cur[n - 1];
...
cur[j] = pre[j] + cur[j - 1];
swap(pre, cur);
- pre는 결국 cur로 대체할 수 있음(이전 row를 날리지 않고 cur에 쌓아가면 됨)
int cur[n - 1];
...
cur[j] += cur[j - 1];