abc 312 D

树状DP
并且左括号多了是可以的，但右括号多了不行
所以让右括号为负一，左括号为正一
这样考虑左括号的情况时，将 i,j 的状态继承到dp[i + 1][j + 1]
同理，右括号时，从 dp[i][1] 开始继承，表示至少有一个左括号
如果画成图的话就是半棵树

// 由顶到底和自底到顶的两种写法（因为是树状的，区别不太明显）
dp[0][0] = 1;
s = ' ' + s;
for (int i = 1; i <= n; i ++) {
    for (int j = 0; j <= n; j ++) {
        if (s[i] != '(') dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % mod;
        if (j && s[i] != ')') dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
    }
}

dp[0][0] = 1;
for (int i = 0; i < n; i ++) {
    for (int j = 0; j <= n; j ++) {
        if (s[i] != '(') dp[i + 1][j] = (dp[i + 1][j] + dp[i][j + 1]) % mod;
        if (j && s[i] != ')') dp[i + 1][j] = (dp[i + 1][j] + dp[i][j - 1]) % mod;
    }
}

abc 311 D

简单bfs

abc 310 D

纯暴力TLE了
所以需要剪枝，考虑新一个组或者往旧的组添加，这样不会重复考虑每个组顺序不同的情况
应该时间复杂度 / T!

abc 309 D

用了 Dijkstra，不过这种边权为 1 的情况，没必要，直接 BFS 就行
稍微改一改就是BFS了

abc 308 D

dfs

abc 307 D

经典栈问题，用一个栈存左括号的下标

abc 306 D

一道简单的线性DP
LeetCode的记忆在攻击我