【c++刷题Day2】专题2T4

这是C++刷题的Day2

🕋题目描述
🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀
在回答出第一道灯谜后，小科获得了想要的花灯，花灯造型美观,新颖别致，此时作为好伙伴的小丁也非常想要，卖花灯的叔叔看出了小丁十分羡慕的表情。于是和小丁说：“作为小朋友喜欢猜灯谜是非常棒的事情，我也给你出一个题目，如果你能回答出来的话也可以免费送你一盏花灯哦。“题目是这样的：给定n对小括号，问给出的一个括号序列是否为一种合理的括号序列，以及n对小括号能够组成的合理括号序列有多少种？规定合理的括号序列为：

①：空序列是合理的。

②：如果A和B都是合理的括号序列，那么AB也是合理的。

③：如果A是合理的，那么(A)也是合理的。

比如，给定两对小括号，那么：()()与(())都是合理的。

对于给定的序列是否是合理的，小丁一眼就看出来了，但是对于n对小括号，有多少种合理的括号序列，小丁就有点被难到了，你能帮助小丁处理这个问题么？
输入格式

输入共两行：

第一行：一个整数n，表示小括号对数。

第二行：由n个小括号组成的括号序列，输入只包含小括号，不存在其他字符。
输出格式

输出共两行：

第一行：输出”YES”或”NO”。如果输入的括号序列是合理的，输出”YES”，否则输出”NO”。

第二行：输出n对小括号可以组成的合理括号序列的种数。
输入输出样列
输入样例1：

1
()

输出样例1：

YES
1

输入样例2：

2
))((

输出样例2：

NO
2

说明

【输入输出样例 1 说明】

样例1说明：1对小括号。

很明显()是合理的，1对括号只有1种合理的括号序列为：()

样例1说明：2对小括号。

很明显))((是不合理的，按照给定左右括号顺序不能组成合理的()

2对括号只有2种合理的括号序列，分别为：()()与(())。

【数据规模与约定】

数据范围1 <= N <=20。
🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀
🔑思路

分为两个任务：
（1）检验括号序列：可以用变量解决
（2）统计括号序列方案数：可以用动态规划！

💯CODE代码：

#include 

using namespace std ;

string s ;
int res ;
int f , n ;
const int N = 110 ;
long long dp[N] ;

int main ()
{


	cin >> n >> s ;
	for (int i = 0; i < s.size (); i++)
	{
		if (res < 0)
		{
			f = 1 ;
			break ;
		}
		if (s[i] == '(') res ++ ;
		else if (s[i] == ')') res -- ;
	}
	if (f || res != 0) cout << "NO\n" ;
	else cout << "YES\n" ;
	dp[0] = dp[1] = 1 ;
	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			int k = i - j - 1 ;
			dp[i] += dp[j] * dp[k] ;
		}
	}
	cout << dp[n] ;
	

	return 0 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41