Auto comment: topic has been updated by praveenojha33 (previous revision, new revision, compare).

Suppose the input sequence is S, d(i,j) is the number of trees corresponding to the subsequences Si,Si+1,...,Sj, you can find d(i,i)=1; and Si is not equal to Sj d (i,j)=0 (because the start point and end point should be the same point). In other cases, suppose the first branch returns to the root of the tree at Sk (there must be Si=Sk), then the sequence corresponding to this branch is Si+1...Sk-1, and the number of solutions is d(i+1,k -1); The access sequence corresponding to other branches is Sk,...Sj, and the number of solutions is d(k,j). Thus, in a non-boundary situation, the recursive relationship is;

d(i,j)=sigma{d(i+1,k-1)*d(k,j)|i+2<=k<=j,Si=Sk=Sj}.

Explanation translated from : Explanation Solution code : Solution