Java DP solution O(mn) with O(n) extra space


  • 0
    A

    Hello, everyone.

    Here's another DP solution which only requires to store a single row as an extra space.

    public class Solution {
        public int uniquePaths(int rows, int cols) {
            if (rows == 0 || cols == 0) return 0;
            int[] R1 = new int[cols];
            int[] R2 = new int[cols];
            
            Arrays.fill(R1, 1);
            R2[cols - 1] = 1;
            
            for (int i = rows - 2; i >= 0; --i) {
                for (int j = cols - 2; j >= 0; --j) {
                    R2[j] = R1[j] + R2[j + 1];
                }
                int[] temp = R2;
                R2 = R1;
                R1 = temp;
            }
            
            return Math.max(R1[0], R2[0]);
        }
    }
    

Log in to reply
 

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