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