# Java Dynamic Programming solution with detailed explanation, only need a 1-dimensional array

• 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];
}
``````

}

• That's amazing!!!!

• N[i-1] actually stores the number of path at the next row in a 2-dimensional array

I found this very confusing, or at least I don't understand the term `next row` here. By `next row`, did you mean `last row`? `last row` means you have already run through that row. is this understanding correct? `next row` means you have NOT run through that row yet.

• @rcholic Hi, by next row, I mean when we are calculating `N[i]`, `N[i-1]` actually stored the value of the next row compare to `N[i]`'s current value. When we finish calculating `N[i] += N[i-1]`, `N[i]` now becomes the number of path for next row again, compared with every thing on the right side of `N[i]`.

• @YaokaiYang , What you just said further confirms that `N[i-1]` refers to the last row, not the next row.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.