括号上色用C++怎么写

括号上色用C语言怎么写
括号上色
题目描述
小艺酱又得到了一堆括号。 括号是严格匹配的。 现在给括号进行上色。 上色有三个要求： 1、只有三种上色方案，不上色，上红色，上蓝色。 2、每对括号只有一个上色。 3、相邻的两个括号不能上相同的颜色，但是可以都不上色。 问括号上色有多少种方案？答案对1000000007取模。

输入描述：
输入括号序列s。(2<=|s|<=700)

输出描述：
输出方案数。

示例
输入
(())
输出
12

望采纳

可以使用动态规划来求解这个问题。首先，将问题转化为一个字符串，其中括号用'('和')'表示。然后，定义一个状态表示从字符串的开头到某一个位置为止的括号序列的状态。例如，状态“(()()”表示第一个括号是左括号，第二个括号是右括号，第三个括号是左括号，第四个括号是左括号，第五个括号是右括号，第六个括号还没有见到。

然后，定义状态转移方程。对于每个状态，它都有三种可能的转移方向：不添加新的括号，添加左括号，添加右括号。如果当前状态中左括号的数量大于右括号的数量，则可以添加右括号。如果当前状态中左括号的数量小于等于右括号的数量，则可以添加左括号。

最后，计算最终的答案。最终的答案就是从起始状态开始，通过状态转移方程，转移到最终状态的方案数。

#include 
using namespace std;

const int MAXN = 100;

// 定义状态
int dp[MAXN][MAXN][4];

int main()
{
    string s;
    cin >> s;
    // 只有一对括号
    if (s.size() <= 2) {
        cout << 1 << endl;
        return 0;
    }

    // 初始化状态：dp[i][i+1][0] = 1
    for (int i = 0; i < s.size(); i++) {
        dp[i][i + 1][0] = 1;
    }

    // 动态规划转移：dp[i][j][0] = dp[i][k][0] + dp[k][j][0] + dp[k][j][1] + dp[k][j][2]
    for (int len = 2; len < s.size(); len++) {
        for (int i = 0; i + len < s.size(); i++) {
            for (int k = i + 1; k < i + len; k++) {
                dp[i][i + len][0] += dp[i][k][0] + dp[k][i + len][0];
                dp[i][i + len][1] += dp[i][k][0] + dp[k][i + len][1];
                dp[i][i + len][2] += dp[i][k][0] + dp[k][i + len][2];
            }
        }
    }

    // 输出结果
    cout << dp[0][s.size() - 1][0] << endl;
    return 0;
}

洛谷的原题，也有题解，可以去翻翻看，我博客里是Python的解法，思路应该是一致的