Iterative dp cpp code with clear explanation


  • 0
    C
    class Solution {
    public:
    
        // numTrees(1, n) = 
        // sum( numTrees(1, i-1)*numTrees(i+1, n) ), 1<=i<=n
    
        // in fact, numTrees only relies on the length of the inteval
        // so, numTrees(n) = 
        // 0 when n=1
        // 1 when n=1
        // sum( numTrees(i)*numTrees(n-1-i) ), 0<=i<n
    
        int numTrees(int n) 
        {
            vector<int> cnt(n+1, 0);
            cnt[0] = cnt[1] = 1;
            
            for(int i=2; i<=n; i++)
                for(int j=0; j<i; j++)
                    cnt[i] += (cnt[j]*cnt[i-1-j]);
            
            return cnt[n];
        }
    };

Log in to reply
 

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