程序填空题：求解拆分集合为相等的子集合问题（动态规划法）

求解拆分集合为相等的子集合问题。将1～n的连续整数组成的集合划分为两个子集合，且保证每个集合的数字和相等。例如：对于n=4，对应的集合{1,2,3,4}能被划分为{1,4}、{2,3}两个集合，使得1＋4＝2＋3，且划分方案只有这一种。

```c++
#include
#include
#include
#define MAXN 20

using namespace std;
int dp[MAXN*MAXN/2][MAXN*MAXN/2];

int split(int n);

int main()
{
int n;
cin>>n;
cout< return 0;
}

int split(int n) //求解算法
{ int i,j;
int sum=n*(n+1)/2;
if(sum%2!=0)
return 0;
sum=sum/2;
memset(dp,0,sizeof(dp));
for(i=0;i<=n;i++)
;
for (i=1;i<=n;i++)
for(j=1;j<=sum;j++)
{
if (i>sum)
dp[i][j]=;
else
dp[i][j]=;
}
return ;
}
```
### 输入格式:

输入正整数n（测试数据已确保{1,2,3,…,n}的和是2的倍数。）

```in
3
```

### 输出格式:

输出拆分方案数。（可划分方案{1,2}、{3}）

```out
1
```





答案：
第1空：dp[i][0]=1

第2空：dp[i-1][j]

第3空：dp[i-1][j]+dp[i-1][j-i]

第4空：dp[n][sum]/2