Java DP solution with complexity O(n*m)


  • 59
    Y
     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.


  • 40
    Z

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

  • 0
    W

    cool ! well done


  • 0
    Y
    This post is deleted!

  • 0
    L

    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?


  • 0
    S

    brilliant!brilliant!brilliant!


  • 0
    S

    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.


  • 0
    G
    This post is deleted!

  • 3
    H

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

  • 1
    M

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

  • 0
    L
    This post is deleted!

  • 15

    alt text


  • 0
    S

    @hphepei your code is the same as mine


  • 0
    F

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

  • 0
    A

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


Log in to reply
 

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