首页 > 牛牛数括号
开通博客写题解
头像 coder+9
发表于 2021-11-10 21:15:25
开头感谢提交列表里的大佬们，以及题解里大佬提供的思路。 本题的思路是这样的，自底向上递推出s1和s2串的合法括号匹配数， 比如本题中有两个变量，i表示s1串下标，j表示s2串下标。 我们假设状态dp[i][j]，表示是s1串i到s2串j的左括号>=0的个数。 接下来我们从案例出发： 先从dp[ 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 萝卜朝天椒
发表于 2019-09-04 20:37:50
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][ 展开全文
去ta的博客 赞 (1) 回复(2) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”