Is this called DP? JAVA solution using a map contains number for recursive program


  • 0
    Y
    public class Solution {
    //construct a map which will be used to contain (Key, Values), which 
    //Key stands for the number of Integers, and 
    //Values stands for the number of valid Tree possibilities using the Key
    //e.g. map.put(2,2); means for 2 integers it has 2 valid tree possiblities
    HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
    
    //initialize the map in the constructor
    public Solution(){
        map.put(0,1);
        map.put(1,1);
        map.put(2,2);
    }
    
    public int numTrees(int n) {
        
        if (n<=1) return 1;
        if (n==2) return 2;
        int left;
        int right;
        int result=0;
        
        //the idea is to calculate the numbers of valid tree possiblities 
        //when using 1 as root, 2 as root, 3 as root,...., and n as root
        for (int i=1; i<=n; i++){
            
            //calculate the number of possiblities of the left sub-tree;
            if (map.get(i-1) !=null) {
                //if we already have the number from the map,
                //get that number from the map;
                left=map.get(i-1);
            }
            else{
                //if we do not have the number from the map,
                //we calculate and put the number into the map
                left=numTrees(i-1);
                map.put(i,left);
            }
            
            //the same as calculating the left sub-tree
            if (map.get(n-i) !=null) {
                right=map.get(n-i);
            }
            else{
                right=numTrees(n-i);
                map.put(n-i,right);
            }
            
            //result should be left * right;
            result+=left*right;
            
        }
        return result;
        
    }
    

    }


  • 0

    seems not like a dp solution... dp focus on the relationship between current and previous step/status or under what condition we need to update the current value. from my understanding, it's different from recursive solution

    this is my solution using dynamic programming thinking. arr[i] means how many different can be built using i tree node(s)

    public class Solution {
        public int numTrees(int n) {
            if (n == -1) {
                return 0;
            }
            if (n == 0 || n == 1) {
                return 1;
            }
            int[] arr = new int[n + 1];
            arr[0] = 1;
            arr[1] = 1;
            for (int i = 2; i <= n; i++) {
                int sum = 0;
                for (int j = 1; j <= i; j++) {
                    sum += arr[j - 1] * arr[i - j];
                }
                arr[i] = sum;
            }
            return arr[n];
        }
    }

Log in to reply
 

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