题解 | #牛群的配对# 动态规划

类似最长回文子串，稍微变形一下即可

定义 dp[j][i] 为字符串 j到i 的匹配结果

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    bool isValidPairing(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 当这一片段长度为奇数时，匹配不可能成功
                if ((i - j + 1) % 2 != 0) {
                    dp[j][i] = false;
                    continue;
                }
                // 当片段长度为2时单独判断
                // 当片段长度大于2时，外层的匹配结果还要兼顾内层的结果
                if (i - j == 1 && ((s[i] == 'B' && s[j] == 'A') ||
                                   (s[i] == 'D' && s[j] == 'C'))) {
                    dp[j][i] = true;
                } else {
                    if ((s[i] == 'B' && s[j] == 'A') || (s[i] == 'D' && s[j] == 'C')) {
                        dp[j][i] = dp[j + 1][i - 1];
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
};

时间复杂度：O(n^2)，双重循环遍历字符串s

空间复杂度：O(n^2)，存储二维数组dp