本文共 939 字，大约阅读时间需要 3 分钟。

此题采用的DP的思想，即分解为小的问题进行解决，然后又使用了递推和递归的思想，

分析：设输入序列为S，d(i,j)为子序列Si,Si+1,...,Sj对应的树的个数，则边界条件是d(i,i）=1，且Si不等于Sj时d（i,j）=0（因为起点和终点应是同一点）。在其他情况下，设第一个分支在Sk时回到树根（必须有Si=Sk），则这个分支对应的访问序列是Si+1,...,Sk-1,方案数为d(i+1,k-1）；其他分支对应的访问序列为Sk,...,Sj,方案数为d(i+1，k-1)；其他分支对应的访问序列为Sk,...,Sj,方案数为d（k,j)。这样，在非边界情况，递推关系为d(i,j)=sum{d(i+1,k-1)*d(k,j)|i+2<=k<=j,Si=Sk=Sj}.

代码如下：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
           
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/ONE_PIECE_HMH/article/details/45599135 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！