My Simple Java Solution


  • 0

    The equation for DP is: dp[i][j] = dp[i][j-1] + dp[i-1][j].
    Since we are only going to use the level i to derive level i+1, there is no need for us to create a m*n 2-D array.

        public int uniquePaths(int m, int n) {
            int[] dp = new int[n];
            Arrays.fill(dp, 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.