问题1024--遍历多叉树

1024: 遍历多叉树

时间限制: 1 Sec  内存限制: 128 MB
提交: 45  解决: 25
[提交] [状态] [讨论版] [命题人:]

题目描述

对于一棵多叉树,可以进行先序遍历

每次递归,1.遍历根, 2. 遍历左边第一个儿子,并对这个儿子结点继续依据先序遍历的规则遍历, 3. 遍历从左到右第二个儿子,并对这个儿子结点继续依据先序遍历的规则遍历, 4. 。。。 5. 遍历从左到右最后一个儿子,并对这个儿子结点继续依据先序遍历的规则遍历。

有一次罗老师写了一个程序对一棵多叉树进行先序遍历,每到一个结点,就输出该结点的结点字母,得到如下序列: ABABABA

但这个时候罗老师又有一个困惑,这个遍历结果的二叉树显然有多种形状,具体有5种,如下图所示:


这里注意,如果某个节点下面只有一个直接儿子,那么不用考虑这个儿子在左边还是右边, 但如果这个结点下面有多个直接儿子,那么他们相对位置不一样算不同方案,比如(c), (d)就算不同方案

罗老师想知道,给定一种遍历的结果,问这样的多叉树方案有多少种。这个结果可能会很大,那么结果要对 1000000000取余。如果这个遍历的结果有问题,即不是合法的遍历结果,那么输出0

输入

输入一行字符串,全部由大写字母构成,长度不超过300

输出

输出方案数,如题目所述。

样例输入 Copy

ABABABA

样例输出 Copy

5

提示

【样例说明】

输入AB

输出0

题解:

dp三要素,状态,转移,初值终值

树形类DP最好写成递归形式

那么要将(1, n)分成多少种方案,可以:

 

ll dfs(int st, int ed){ //st,ed作为起点重点的遍历种类数量

    //printf("st=%d st=%d\n",st,ed);

    if(st==ed) {

        dp[st][ed]=1LL; //初值

        return dp[st][ed];

    }

    if(dp[st][ed]!=-1) return dp[st][ed]; //记忆化

    dp[st][ed]=0LL;

    if(str[st]!=str[ed]){

        return dp[st][ed];

    }

    for(int i=st+1; i<=ed; i++){

        //st作为根

        dp[st][ed]+=dfs(st+1,i)*dfs(i+1,ed);

        //(st+1,i)这段独立一段作为左儿子,特点是只有一个st的直系儿子, str[i]不一定要等于str[st]

        //(i+1,ed)这段作为剩下的兄弟们,这些兄弟可以继续再分出一个儿子,然后剩下的继续兄弟们,特点是最终str[ed]必须要等于str[st],等于str[i+1]

        if(dp[st][ed]>=MOD) dp[st][ed]%=MOD;

    }

    //cout<<st<<" "<<ed<<" "<<dp[st][ed]<<endl;

    return dp[st][ed];

}

 

递归过程中,记录状态,这个状态就是,ij这个区间可以构成多少种方案

递归终点就是一个结点时,只有一种方案

状态转移就是dp[st][ed]+=dfs(st+1,i)*dfs(i+1,ed);

来源/分类