题意
有一块n*2的巧克力，将它分成k块，问有多少种方法。
分析
emmm是dp没错了。
最容易想到的状态定义是f[i][j]，意思是前i行，分成j块的方案数。但是发现没法转移。（后面会说一下为什么···）
我们把状态定义为f[i][j][0]和f[i][j][1]。
f[i][j][0]:前i行分成j块，且第i行的两小块巧克力是没有连在一起的。
f[i][j][1]:前i行分成j块，且第i行的两小块巧克力是连在一起的。
我们来把转移分一下类。
情况1：从i行到i+1行的时候，巧克力的块数多了两块。这说明，第i+1行的两小块一定是分开的，而且没有和第i行的相连。那么转移只有一种情况f[i][j][0]=f[i-1][j-2][0]+f[i-1][j-2][1]
情况2：从i行到i+1行的时候，巧克力的块数多了一块。如果第i+1行的两小块是连在一起的一整块，那么一定没有和i行的相连。既f[i][j][1]=f[i-1][j-1][0]+f[i-1][j-1][1]。如果第i+1行的两小块是分开的，那么一定有一块是和i行相连。既f[i][j][0]=f[i-1][j-1][1]*2+f[i-1][j-1][0]*2
情况3：从i行到i+1行的时候，巧克力的块数没有增加。这就说明第i+1行的一定是和i行相连的。如果第i+1行两小块是分开的，那么第i行一定是分开的。所以f[i][j][0]=f[i-1][j][0]。如果i+1行两小块是和在一起的，那么就要分类讨论。
思路大概就是这个样子。。。
至于为什么简单的定义为f[i][j]没法转移，因为，我试过了···他就是没法转移···········
咳咳不闹，我们来看第三种情况，他的转移是和前一行是分开还是连在一起的有关。所以我们要表示出这个状态。
下面是代码，我尽量写的可读性强一些了···
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std;
const int maxn=+;
const int MOD=;
int n,k,T;
int f[maxn][*maxn][];//0分开，1和起来
int main(){
scanf("%d",&T);
for(int t=;t<=T;t++){
memset(f,,sizeof(f));
scanf("%d%d",&n,&k);
f[][][]=f[][][]=;
for(int i=;i<=n;i++){
f[i][*i][]=;f[i][][]=;
for(int j=;j<*i;j++){
//******第1，2种情况***********
f[i][j][]=(f[i-][j-][]+f[i-][j-][])%MOD;//1.1
f[i][j][]=(f[i-][j-][]*+f[i-][j-][]*)%MOD;//2.1
f[i][j][]=(f[i][j][]+f[i-][j-][]+f[i-][j-][])%MOD;//2.2 //*********第3种情况**************
f[i][j][]=(f[i][j][]+f[i-][j][]*+f[i-][j][])%MOD;
f[i][j][]=(f[i][j][]+f[i-][j][])%MOD;
}
}
int ans=(f[n][k][]+f[n][k][])%MOD;
printf("%d\n",ans);
}
return ;
}