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


  • 0
    Y

    /*
    // 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];
    }
    }


Log in to reply
 

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