题意

给定一个仅包含'('、')'和'?'三种字符构成的字符串，'?'字符可以代替左括号或者右括号。请问该字符串可以代表多少种不同的合法括号序列？

思路

看基本上都写的dp，来个记忆化搜索的代码吧

每个?字符都有两种可能，填左括号或是填右括号，可以枚举填哪个进行记忆化搜索

如何判断是合法的括号序列？只需要维护左括号比右括号多了几个就可以，也就是当前没有配对的右括号个数。假设为val，如果当前是左括号，那么下一次dfs的参数肯定是val+1；如果当前是右括号，下一次dfs参数是val-1，表示可以配对一个左括号。注意这里其实会有不合法情况，就是其实左边是没有左括号的，也就是val为负数的情况，需要在dfs开始就判断下。

边界条件就是如果遍历完了所有的字符串，如果左括号和右括号一样多，就是合法的，返回1；否则，返回0

这里是从1到n写的记忆化搜索，也可以从n到1，一样的思路

注意取模

package main

import "fmt"

func main() {
	/*
		给定一个仅包含'('、')'和'?'三种字符构成的字符串，'?'字符可以代替左括号或者右括号。请问该字符串可以代表多少种不同的合法括号序列？
	*/
	const MOD = 1_000_000_007
	var s string
	fmt.Scan(&s)
	n := len(s)
	s = " " + s
	var dfs func(int, int) int

	/*
		子问题：如果当前字符是?的话填什么 可以填左括号 也可以填右括号
		两种选择
		val表示没有配对的左括号数量
	*/
	dp := make([][]int, n+1)
	for i := 1; i <= n; i ++ {
		dp[i] = make([]int,n+1)
		for j := 0; j <= n; j ++{
			dp[i][j] = -1 
		}
	}
	
	dfs = func(idx int, val int) int {
		if val < 0 {
			return 0
		}
		if idx == n+1 {
			//结束
			if val == 0 {
				return 1
			} else {
				return 0
			}
		}
		if dp[idx][val] != -1 {
			return dp[idx][val]
		}
		var res = 0
		if s[idx] == '?' {
			//这一位填(
			res = (res + dfs(idx+1, val+1)) % MOD
			//这一位填) 
			res = (res + dfs(idx + 1, val - 1 )) % MOD
		}else if s[idx] == '(' {
			res = dfs(idx+1,val+1) 
		}else{
			res = dfs(idx+1,val-1) 
		}
		dp[idx][val] = res
		return res
	}
	fmt.Println(dfs(1,0))
}