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

• 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;

}

}

• 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];
}
}

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