LeetCode 96. Unique Binary Search Trees

• 2020 年 2 月 11 日
• 笔记

题目

第一发超时了，可以用一个数组表示状态，所有相等长度的区间，它的BST数目是一样的。

class Solution {  public:      int vis[10005];      int numTrees(int n) {            if(n<1)              return 0;          vis[1]=1;          return fun(1,n);      }        int fun(int l,int r)      {          if(vis[r-l+1]!=0)          {              return vis[r-l+1];          }          int num=0;          for(int i=l;i<=r;i++)          {                int lefts = fun(l,i-1);              int rights = fun(i+1,r);                num += lefts * rights;            }          if(num==0)              num++;            vis[r-l+1]=num;          return num;      }  };