题目省略
大体思路:多状态的动态规划,以一对括号为动态规划最小单元,从第一个出现的右括号所在的那对括号开始,从里向外。
动态方程为:
一、如果当前括号里面还有括号:
当前左括号为红色的总可能方案=里面那个左括号为红色的总方案+里面那个左括号为绿色的总方案2+里面那个左括号为蓝色的总方案2
当前左括号为绿色的总可能方案=里面那个左括号为红色的总方案+里面那个左括号为蓝色的总方案
当前左括号为蓝色的总可能方案=里面那个左括号为红色的总方案+里面那个左括号为绿色的总方案
二、如果当前括号在前面计算过的括号的右边,如(())()中的右边那对括号:
当前左括号为红色的总可能方案=前面括号所有方案总和+2
1