# Java DP solution with complexity O(n*m)

• `````` public class Solution {
public int uniquePaths(int m, int n) {
Integer[][] map = new Integer[m][n];
for(int i = 0; i<m;i++){
map[i][0] = 1;
}
for(int j= 0;j<n;j++){
map[0][j]=1;
}
for(int i = 1;i<m;i++){
for(int j = 1;j<n;j++){
map[i][j] = map[i-1][j]+map[i][j-1];
}
}
return map[m-1][n-1];
}
}
``````

The assumptions are

1. When (n==0||m==0) the function always returns 1 since the robot
can't go left or up.
2. For all other cells. The result = uniquePaths(m-1,n)+uniquePaths(m,n-1)

Therefore I populated the edges with 1 first and use DP to get the full 2-D array.

Please give any suggestions on improving the code.

• when `(m==0 || n== 0)`, my understanding is there will be no way to go down or right, so return 0.

a little optimization of the space, 1-D array:

``````public int uniquePaths(int m, int n) {
if (m == 0 || n == 0) {
return 0;
}
if (m == 1 || n == 1) {
return 1;
}

int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}``````

• cool ! well done

• This post is deleted!

• for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1];
}
}
Can you give an explanation about it?

• brilliant!brilliant!brilliant!

• calculate row by row. the jth cell of (i+1)th row can be reached either from the jth cell of ith row down by one, or from the (j-1)th cell of ith row down by one and right by one.

• This post is deleted!

• You can simply initial the first column and first row in the same loop of creating your record table without using the extra two loops.

``````public int uniquePaths(int m, int n) {
int[][] tab = new int[m][n];

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

return tab[m-1][n-1];
}``````

• Much more concise version:

``````	public int uniquePaths(int m, int n) {

int[][] dp = new int[m][n];

for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
dp[i][j] = i == 0 || j == 0 ? 1 : dp[i - 1][j] + dp[i][j - 1];

return dp[m - 1][n - 1];
}``````

• This post is deleted!

• @hphepei your code is the same as mine

• It is possible to change the space complexity to O(n) by using mod operation -- only storing two rows at a time, all the previous rows are not needed while the DP proceeds.

``````public class Solution {
public int uniquePaths(int m, int n) {
if (m == 0 || n == 0) return 0;
int[][] f = new int[2][n];

for (int i = 0; i < m; i++) {
f[i % 2][0] = 1;
for (int j = 1; j < n; j++) {
if (i == 0)
f[i % 2][j] = 1;
else
f[i % 2][j] = f[(i - 1) % 2][j] + f[i % 2][j - 1];
}
}
return f[(m - 1) % 2][n - 1];
}
}
``````

• @zihan (m==0 || n== 0) it has one unique path that is row 0 and column 0

• @Zihan

``````public int uniquePaths(int m, int n) {
if (m == 0 || n == 0) {
return 0;
}
if (m == 1 || n == 1) {
return 1;
}

int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
``````

Thinking a lot's time.I think:
in this line: `dp[j] += dp[j - 1];` That's mean's add it's up num and left num.
just like `path[i][j] = path[i-1][j] + path[i][j-1]`:
`path[i-1][j]` is up num.
`path[i][j-1]` is left num.

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