Solution based on dynamic programming O(n^2) instead of exponencial

Question

class Solution {

    public:

        int numTrees(int n) {

            // We use a vector to memoize subproblem's results:
            int results[n + 1];
            results[0] = 1;
            for (int i = 1; i <= n; ++i) {

                // Every iteration uses previous iterations results:
                results[i] = numTreesRec(results, i);
            }

            return results[n];
        }

        int numTreesRec(const int* results, int n) {

            int res = 0;

            // Calculates the combinations generated when the root node is
            // one on the left half of the set:
            int hn = n / 2;
            for (int i = 0; i < n / 2; ++i) {

                res += results[i] * results[n - (i + 1)];
            }

            // For combinations generated when the root node is  one of the
            // right half we know that is the same as the former step, hence
            // we just multiply by two:
            res *= 2;

            // If n is odd we need to add the combinations when the middle node is root:
            if (n & 1) {

                int i = n / 2;
                res += results[i] * results[n - (i + 1)];
            }

            return res;
        }
    };