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

  • 0
    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(){
    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;
                //if we do not have the number from the map,
                //we calculate and put the number into the map
            //the same as calculating the left sub-tree
            if (map.get(n-i) !=null) {
            //result should be 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.