请同学们看看这个每日一练，真的属于题干都没看懂

Question

这个问题的实例输出我是真的没搞懂，数学公式推导我都写不出来，真心不会

Answer 1

  用动态规划来解决。可以用dp[i][j]表示区间[i,j]内括号上色的方案数。我们将左括号用数字1表示，右括号用数字2表示。那么有三种上色方案：
1.什么都不涂，表示为0
2.涂成1，表示为1
3.涂成2，表示为2
  对于一个区间[i,j]，我们可以枚举该区间内第一对括号的位置k，那么有两种情况：
1.第k个位置上的左括号和区间[j]上的右括号匹配，即s[k]为1，s[j]为2。那么区间[i,j]的颜色只有两种情况，一种是将s[k]和s[j]都涂成1，另一种是将它们都涂成2。因 
   此，我们可以得到以下递推式：
dp[i][j] = (dp[i][k-1]*dp[k+1][j-1]*2) % mod

2区间[i,j]内没有可以匹配的括号对。那么我们可以将区间分成两个子区间，分别求出它们上色的方案数，然后将它们相乘。因此，我们可以得到以下递推式：
    
dp[i][j] = (dp[i][k-1]*dp[k][j]+dp[i][k]*dp[k+1][j]) % mod

其中，k为区间[i,j]内第一对括号的位置。具体实现时，我们可以用一个栈来找到区间内第一对括号的位置。
最终答案为dp[1][n]，其中n为字符串s的长度。
下面是程序，可以参考

#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
const int mod = 100000007;
const int MAXN = 705;
int dp[MAXN][MAXN]; // dp数组，表示区间[i,j]内括号上色的方案数
char s[MAXN]; // 输入的括号序列

int main() {
    cin >> s + 1; // 为了方便，从s[1]开始读入括号序列
    int n = strlen(s + 1);
    stack<int> st;
    // 找到每一对括号的位置
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(') {
            st.push(i);
        } else {
            int j = st.top();
            st.pop();
            dp[j][i] = 1;
        }
    }
    // 动态规划
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            if (dp[i][j] != 0) { // 如果区间[i,j]已经匹配
                for (int k = i; k < j; k++) {
                    if (dp[i][k] != 0 && dp[k+1][j-1] != 0) {
                        // 如果区间[i,k]和区间[k+1,j-1]都已经匹配
                        dp[i][j] = (dp[i][j] + dp[i][k]*dp[k+1][j-1]*2) % mod;
                    }
                }
            } else {
                for (int k = i; k < j; k++) {
                    if (dp[i][k] != 0) {
                        dp[i][j] = (dp[i][j] + dp[i][k]*dp[k+1][j]) % mod;
                    }
                    if (dp[k+1][j] != 0) {
                        dp[i][j] = (dp[i][j] + dp[i][k+1]*dp[k+2][j]) % mod;
                    }
                }
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}