Easiest c++ solution with comments

programming
amazon
interview-questions
Tags: #<Tag:0x00007f241e1ed4c8> #<Tag:0x00007f241e1ed2e8> #<Tag:0x00007f241e1ecde8>

#1

int Solution::numTrees(int A) {

int dp[A+1];

for(int i=0;i<=A;i++)
    dp[i]=0;

dp[0]=1;// only one null comb. possible
dp[1]=1;//only one comb. possible

for(int i=1;i<=A;i++){
    dp[i]=0;// initialization
    for(int j=1;j<=i;j++){
        
        dp[i]=dp[i]+dp[j-1]*dp[i-j];// j-1 on the left subtree and i-j on the right subtree; multiplication will give total no. f possible combinations they can have and then we add this and change value of j for next set of combinations;
    }
}


return dp[A];

}