<p>Dynamic programming problems can be solved by two approach</p>
<p>1) Top Down approach (on Demand memorization methods)<br>
2) bottom up approach(tabulation Method)</p>
<p><strong>Plain Description </strong></p>
<p>for a balanced binary search tree the difference b/w height of left and right subtree should be atmost 1</p>
<p>n = 0 output = 1</p>
<p>now for n = 1<br>
output = 1</p>
<p>for n = 2 the valid options are 0,1 and 1,0 where two values are nodes in left and right so <br>
output will be 1*1 + 1*1 = 2</p>
<p>for n = 3 the valid options are 1,1 only<br>
so output be 1*1 = 1</p>
<p>for n = 4 the valid options are 1,2 , 2,1 so <br>
output = 2*1 + 1*2 = 4</p>
<p>for n = 5 valid options are 1,3, 2,2, 3,1<br>
output = 1*1 + 2*2 + 1*1 = 6</p>
<p>for n = 6 valid options are 2,3 , 3,2 <br>
output = 2*1 + 1*2 = 4</p>
<p>for n = 7 valid options are 2,4 , 3,3 , 4,2<br>
output = 2*4 + 1*1 + 4*2 = 17</p>
<p> </p>
<p><strong>Top Down Approach</strong></p>
<p>int countNoOfTreeUsingDP(int * array ,int N) {</p>
<p> if(array[N] ==0){</p>
<p> if(N >=0)</p>
<p> array[0] =1;</p>
<p> if(N >=1)</p>
<p> array[1] =1;</p>
<p> if(N >=2)</p>
<p> array[2]= 2;</p>
<p> if(N >= 3)</p>
<p> array[3] =1;</p>
<p> if(N<=3)</p>
<p> return array[N];</p>
<p> int sum =0;</p>
<p> int left =0;</p>
<p> int right =0;</p>
<p> if( N %2 !=0) {</p>
<p> left= countNoOfTreeUsingDP(array, N/2);</p>
<p> right = countNoOfTreeUsingDP(array,N/2);</p>
<p> sum += left * right;</p>
<p> left = countNoOfTreeUsingDP(array,N/2 -1);</p>
<p> right = countNoOfTreeUsingDP(array,N/2 +1);</p>
<p> sum += 2*(left * right);</p>
<p> array[N] = sum;</p>
<p> }</p>
<p> else {</p>
<p> left = countNoOfTreeUsingDP(array,N/2 -1);</p>
<p> right = countNoOfTreeUsingDP(array,N/2);</p>
<p> sum += sum + 2*(left*right);</p>
<p> array[N]= sum;</p>
<p> }</p>
<p> return sum;</p>
<p> }</p>
<p> else {</p>
<p> return array[N];</p>
<p> }</p>
<p>}</p>
<p><strong>Bottom Up Approach</strong></p>
<p>int countNoOfTreeUsingDP1(int * array ,int N) {</p>
<p> if(N>=0)</p>
<p> array[0]=1;</p>
<p> if(N>=1)</p>
<p> array[1]=1;</p>
<p> if(N>=2)</p>
<p> array[2] =2;</p>
<p> if(N>=3)</p>
<p> array[3] =1;</p>
<p> if(N<=3)</p>
<p> return array[N];</p>
<p> for(int i=4; i<=N; i++) { </p>
<p> int k = i/2;</p>
<p> if(i%2 ==0)</p>
<p> array[i] = 2 * array[k] * array[N-1-k];</p>
<p> else</p>
<p> array[i] = array[k] * array[k] + 2 * array[k-1] * array[k+1];</p>
<p> }</p>
<p> return array[N];</p>
<p>}</p>
<p> </p>
