C++ DP Solution with O(n^2) time complexity and O(n) space complexity


  • 0
    E
    class Solution {
    public:
        int numTrees(int n) {
            if(n<=2) return n;
            vector<int> dp(n+1,0);
            dp[0] = 0;
            dp[1] = 1;
            dp[2] = 2;
            for(int i = 3; i <= n; i++)
                for(int j = 0; j <= i-1; j++){
                    if(j==0 || j==i-1) dp[i] += dp[i-1];
                    else dp[i] += (dp[j] * dp[i-1-j]);
                }
            return dp[n];
        }
    };
    

Log in to reply
 

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