描述
我们定义长度为2n的不一定合法括号序列为左右括号个数均为n的序列。
我们定义不一定合法括号序列的bad指数为这个序列当中没有对应右括号的左括号的个数。
给出n,k。求bad指数为k的长度为2n的不一定合法括号序列的个数。
由于答案很大，你只需要输出对109 + 7取余的结果。
输入
一行两个整数n,k
对于30%的数据 1 ≤ k ≤ n ≤ 10
对于100%的数据 1 ≤ k ≤ n ≤ 300
输出
一个整数表示答案。
样例输入
2 1
样例输出
3
思路:
动态规划方法，三元组(i,j,k)刻画状态，三元组表示考虑到第i个位置，已经出现了左括号j个，未匹配的左括号k个。
转移方程：
左括号 ( 坏数+1
dp(i+1,j+1,k+1) = dp(i+1,j+1,k+1) + dp(i,j,k)
右括号 ( 坏数-1
dp(i+1,j,k-1) = dp(i+1,j,k-1) + dp(i,j,k)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N = 305;
const int mod = 1e9 + 7;
int dp[N*2][N][N];
int n,k;
int main()
{
scanf("%d%d", &n, &k);
int m = 2*n;
dp[0][0][0] = 1;
for(int i = 1; i <= m; i++)
{
for(int j = 0; j <= min(n,i); j++)
{
for(int s = 0; s <= j; s++)
{
dp[i+1][j+1][s+1] += dp[i][j][s];
dp[i+1][j][max(0,s-1)] += dp[i][j][s];
dp[i+1][j+1][s+1] %= mod;
dp[i+1][j][max(0,s-1)] %= mod;
/*
if(s == 0)
dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1];
else
{
if(j == 0)
dp[i][j][s] = dp[i-1][j][s+1];
else
dp[i][j][s] = dp[i-1][j-1][s-1] + dp[i-1][j][s+1];
}
dp[i][j][s] %= mod;
*/
}
}
}
printf("%d
", dp[m][n][k]);
return 0;
}