# Easy understand Java O(n) space DP rolling array technique

• 1st solution is O(m*n) space and can be optimized to the 2nd O(n) space using rolling array technique.
Is there a way to further optimize it to O(1) space dp ?

`````` public class Solution {
public int uniquePaths(int m, int n) {
if (m == 0 || n == 0) {
return 0;
}
int[][] paths = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
paths[i][j] = 1;
} else {
paths[i][j] = paths[i - 1][j] + paths[i][j - 1];
}
}
}
return paths[m - 1][n - 1];
}
}

public class Solution {
public int uniquePaths(int m, int n) {
if (m == 0 || n == 0) {
return 0;
}
int[][] paths = new int[2][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
paths[i % 2][j] = 1;
} else {
paths[i % 2][j] = paths[(i - 1) % 2][j] + paths[i % 2][j - 1];
}
}
}
return paths[(m - 1) % 2][n - 1];
}
}``````

• I don't know if it could be further optimized to O(1) space, but it can be optimized to O(1n) space (i.e. not need O(2n) space)
The idea is like this:
Since we only need to know `N[m-1][n-1]` for a m*n grid, it is a waste of space to keep the whole 2-dimensional array. And we also know that `N[i][j] = N[i-1][j] + N[i][j-1]`, so if we use only a one dimensional array and let `N[i] = N[i] + N[i-1]`. i.e. the `N[i]` at the left side of the equation and `N[i-1]` actually stores the number of path at the next row in a 2-dimensional array, and `N[i]` at the right side of the equation stores the number of paths at the current row in a 2-dimensional array. So in general, every element on the left side of `N[i]` in the 1 dimensional array is actually the value at the next row if in a 2-dimensional array.
By filling the array from left to right, we will never rewrite a value before we making use of it.

``````public class Solution {
public int uniquePaths(int m, int n) {
/*
Dynamic Programming
Bottom-up approach
If we use Num[n] to denote the number of paths and we fill this form from left to right, we will never rewrite a value before we make use of it.
O(mn) time and O(n) space
*/
if (m == 0 || n == 0){
return 0;
}

int[] Num = new int[n];
for (int i = 0; i < m; i ++){
for (int j = 0; j < n; j++){
if (i == 0 || j == 0){
Num[j] = 1;
}

else {
Num[j] += Num[j-1];
}
}
}

return Num[n-1];
}
``````

}