dp计数
牛牛数括号
http://www.nowcoder.com/questionTerminal/145ced9bc6854a69a77f7c55d62faf2c
dp[i][j]表示在s1中选择前i个字符，在s2中选择前j个字符，能够成合法序列的方案数（这里的合法指的是每个')'都能找到一个'('与之对应）。
一个长度为i+j的括号序是从(i-1,j)和(i,j-1)转移过来的,所以dp[i][j]=dp[i-1][j]+dp[i][j-1]。
判断dp[i][j]是否合法，只需要判断s1和s2中的'('的数量是否比')'多，其他不用管。假如s1是(,s2是))(,这样当然构造不出一个合法序，但是dp[i-1][j]和dp[i][j-1]一定也为0.就是说如果dp[i][j]不合法，它一定不能从合法的状态转移过来。
另外需要注意的是，这题卡内存。
三奇智元机器人科技有限公司公司福利 69人发布
查看1道真题和解析