Optimised Java DP solution


  • 0
    C

    I found many people used double for loops in their DP solution, in which the second iteration j goes from 0 to i.

    public int numTrees(int n) {
            
            if (n <= 0) return 0;
            if (n == 1) return 1;
            
            // dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0] 
            // i: 0 --> n - 1; j: n - 1 - i 
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
           
            for (int i = 2; i < dp.length; i ++) {          
                for (int j = 0; j <= i - 1; j ++) 
                    dp[i] += dp[j] * dp[(i - 1) - j];         
            }
    
            return dp[n];
       }
    

    However, according to the symmetric properties of BST, dp[i]*dp[j] = dp[j]*dp[i], for example, dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0] = dp[0] * dp[2] * 2 + dp[1]*dp[1]. Therefore, we can further optimise the DP solution:

    public int numTrees(int n) {
            
             if (n <= 0) return 0;
             if (n == 1) return 1;
             
             // dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0] 
             // i: 0 --> n - 1; j: n - 1 - i 
             
             int[] dp = new int[n + 1];
             dp[0] = 1;
             dp[1] = 1;
             
             /*
             for (int i = 2; i < dp.length; i ++) {          
                 for (int j = 0; j <= i - 1; j ++) 
                     dp[i] += dp[j] * dp[(i - 1) - j];         
             }
             */
             
             // further optimise : only caculate half (using the symmetric property of BST)
             for (int i = 2; i < dp.length; i ++) { 
                 int j = 0;
                 for (; j < (i - 1) / 2; j ++) 
                     dp[i] += dp[j] * dp[(i - 1) - j] * 2;  
                 int temp = dp[j] * dp[(i - 1) - j];
                 dp[i] += (j == i - 1 - j) ? temp : temp * 2;
             }
                    
             return dp[n];
        }
    

Log in to reply
 

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