dp thought O(n) time O(n) space
| 41 | |
| 42 | // dp thought O(n) time O(n) space |
| 43 | int numTrees_dp(int n) { |
| 44 | vector<int> dp (n+1,0); |
| 45 | dp[0] = dp[1] = 1; |
| 46 | for (int i=2; i<=n; i ++ ) { |
| 47 | for (int j=0; j<i; j ++ ) { |
| 48 | dp[i] += dp[j] * dp[i - j - 1]; |
| 49 | } |
| 50 | } |
| 51 | return dp[n]; |
| 52 | } |
| 53 | |
| 54 | // cantalan tree |
| 55 | // http://www-math.mit.edu/~rstan/ec/catalan.pdf |
nothing calls this directly
no outgoing calls
no test coverage detected