my solution


  • 0
    P
    class Solution {
    public:
        int numTrees(int n) {
            vector<int> vi{1,1};
            for(int i=2;i<=n;++i){
                int sum=0;
                for(int t=0;t<i;++t){
                    sum+=vi[t]*vi[i-1-t];
                }
                vi.push_back(sum);
            }
            return vi[n];
        }
    };
    

    a(n)=a0a(n-1)+……+a(n-1)a0;
    you can draw tree tree to understand it. : )
    (sorry for terrible edition)

    for example n=3;

         _ _    3                _ 2  _                 1    ____
        |   2|                  |1|  |3|                    |2    |
        |1_ _|                                              |    3|
          a2  * a0              a1 * a1                a0 *    a2

Log in to reply
 

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