Simple 1ms code of DP in 9 lines


  • 0

    The running time of my following code actually surprised me. It takes only 1 ms.

    int numTrees(int n) {
            vector<int> count(n + 1, 1);
            for (int i = 2; i < n + 1; i++) {
                count[i] = 0;
                for (int j = 0; j < i; j++)
                    count[i] += (count[j] * count[i - 1 - j]);
            }
            return count[n];
        }

Log in to reply
 

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