跟动态规划干上了，新的一道动态规划题目
晓萌希望将1到N的连续整数组成的集合划分成两个子集合，且保证每个集合的数字和是相等。例如，对于N=3，对应的集合{1，2，3}能被划分成{3} 和 {1,2}两个子集合.
这两个子集合中元素分别的和是相等的。
对于N=3，我们只有一种划分方法，而对于N=7时，我们将有4种划分的方案。
输入包括一行，仅一个整数，表示N的值（1≤N≤39）。
输出包括一行，仅一个整数，晓萌可以划分对应N的集合的方案的个数。当没发划分时，输出0。
样例输入
7
样例输出
4
解析
这题一看，没办法马上想出动态规划的方法，因为N=7和N=6没什么联系，所以不能通过N=6求N=7
然后打算使用递归来做，这个题目的意思就是在1-N的N个数里面任取k个数，使得k个数之和等于这N个数的和的一半，求有多少种取法，最后的结果减半就可以了。
定义一个数组int dp[1000][50]={0}; dp[x][y]代表在1-y的y个数里面取数，总和是x的情况有dp[x][y]种
用函数F(i,j)来求dp[i][j]，求出来的每个dp[i][j]记录下来，如果之前求过就不需要再继续求
函数F分为4种情况
1.dp[i][j]已经求出，直接返回即可
2.i>=j的时候，dp[i][j]=不取j的情况 F(i,j-1) +取j的情况 F(i-j,j-1); i<j时，dp[i][j]=dp[i][j-1];
3.j为0的时候，无数可取，返回0
4.i为0的时候，说明刚好取够，此时dp[i][j]=1，返回1
最后实现的时候，运行超时，说明这个方法还有待改进，等下次有空再发新的
优化后版本计蒜客 等和的分隔子集(优化)
代码
int dp[1000][50]={0};
int F(int number,int n)
{
if(dp[number][n]!=0)
{
}
else if(number==0)
{
dp[number][n]=1;
}
else if(n==0)
{
return 0;
}
else if(number>=n)
{
dp[number][n]=F(number,n-1)+F(number-n,n-1);
}
else
{
dp[number][n]=F(number,n-1);
}
return dp[number][n];
}
int main()
{
int N;
scanf("%d",&N);
int number=N*(N+1)/2;
if(number%2==0)
{
number=number/2;
printf("%d\n",F(number,N)/2);
}
else
{
printf("0\n");
}
return 0;}
