Java DP solution with only one loop


  • 0
    W
    public class Solution {
        int[][] map;
        public int numTrees(int n) {
            map = new int[n][n];
            return num(1, n);
        }
        
        public int num(int m, int n){
            if(m == n)
                return 1;
            if(map[m - 1][n - 1] != 0)
                return map[m - 1][n - 1];
            int sum = 0;
            for(int i = m; i <= n; i++){
                if(i == m)
                    sum += num(i + 1, n);
                else if(i == n)
                    sum += num(m, i - 1);
                else
                    sum += num(m, i - 1) * num(i + 1, n);
            }
            map[m - 1][n - 1] = sum;
            return sum;
        }
    }

  • 0
    M

    What is the time complexity of your algorithm? Could u give an explanation? Thank u.


Log in to reply
 

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