动态规划算法，计算平衡二叉搜索树的数量

Question

给定节点的个数n，计算能产生的不同的平衡二叉搜索树的数量T(n)

Answer 1

leetcode 96 Unique Binary Search Trees
是这题吗？
python：

class Solution(object):
    def __init__(self):
        self.map={}
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<=1 :
            return 1
        if n not in self.map:
            ans=0
            for i in range(0,n):
                ans+=(self.numTrees(i)*self.numTrees(n-1-i))
            self.map[n]=ans
        else :
            ans=self.map[n]
        return ans

java:
写java的时候还不太理解动态规划，写的比较丑，自行优化

public class Solution {
    public int numTrees(int n) {
        return f(n,new HashMap<Integer, Integer>());
    }
    public int f(int n,Map<Integer,Integer> map){
        if (map.get(n)!=null) {
            return map.get(n);
        }else {
            
            if (n==1||n==0) {
                return 1;
            }else {
                int sum=0;
                for (int i = 0; i < n; i++) {
                    int left=f(i,map);
                    int right=f((n-1-i),map);
                    sum+=(left*right);
                }
                map.put(n,sum);
                return sum;
            }
        }
    }
}