# two DP solutions in Java using O(m*n) space and O(n) space respectively

• /*
// time complexity: O(m * n)
// space complexity: O(m * n)
public class Solution {
public int uniquePaths(int m, int n) {
if (m < 1 || n < 1) {
return 0;
}
// use the dp[i][j] to specify the number of path reaching [i][j]
// dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
int[][] dp = new int[m][n];
for (int j = 0; j < n; ++j) {
dp[0][j] = 1;
}
for (int i = 0; i < m; ++i) {
dp[i][0] = 1;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
*/

// improvement space complexity to O(n) from original O(m * n)
// time complexity: O(m * n)
// space complexity: O(n)
public class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
for (int j = 0; j < n; ++j) {
dp[j] = 1;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
}

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