题意解读 题目说一个字符串中由3种字符组成：（，）和？ 当这一位是问号时，可以是 ( 和 ) 中的一种，问一共有多少种方案使得最后满足 括号字符串的条件。 思路 一般看到这种方案数的问题，都用 dp 做。需要列出转移式子。 我们看到这题就会想，可不可以用DP记录当前在第I的位置能不能有J个左括号和K个右括号 于是! DP[I][J][K]诞生了。可是该怎么优化呢？我们要手动模拟一下，寻找方法。 不难发现： 也就是j>=k 于是就可以用j-k作为第二维。刚好 所以N方能过。 * * 完整代码 总结 遇到这类题可以从题目给的数据范围入手，特别是方案数、可行性、最多的字眼。