官方题解解释太好了。自己咋就想不出来这递推式呢emmm

 

 

 

 

 

 

 1 class Solution {
 2 public:
 3     int numTrees(int n) {
 4         vector<int> G(n + 1, 0);
 5         G[0] = 1;
 6         G[1] = 1;
 7 
 8         for (int i = 2; i <= n; ++i) {  i对应公式中的n,j对应公式中的i
 9             for (int j = 1; j <= i; ++j) {
10                 G[i] += G[j - 1] * G[i - j];
11             }
12         }
13         return G[n];
14     }
15 };