跟動態(tài)規(guī)劃干上了发钝，新的一道動態(tài)規(guī)劃題目
曉萌希望將1到N的連續(xù)整數(shù)組成的集合劃分成兩個子集合，且保證每個集合的數(shù)字和是相等漩符。例如一喘，對于N=3，對應(yīng)的集合{1嗜暴，2凸克，3}能被劃分成{3} 和 {1,2}兩個子集合.
這兩個子集合中元素分別的和是相等的。
對于N=3闷沥，我們只有一種劃分方法萎战，而對于N=7時，我們將有4種劃分的方案狐赡。
輸入包括一行撞鹉，僅一個整數(shù)疟丙，表示N的值（1≤N≤39）。
輸出包括一行鸟雏，僅一個整數(shù)享郊，曉萌可以劃分對應(yīng)N的集合的方案的個數(shù)。當沒發(fā)劃分時孝鹊，輸出0炊琉。
樣例輸入
7
樣例輸出
4
解析
這題一看，沒辦法馬上想出動態(tài)規(guī)劃的方法又活，因為N=7和N=6沒什么聯(lián)系苔咪，所以不能通過N=6求N=7
然后打算使用遞歸來做，這個題目的意思就是在1-N的N個數(shù)里面任取k個數(shù)柳骄，使得k個數(shù)之和等于這N個數(shù)的和的一半团赏，求有多少種取法，最后的結(jié)果減半就可以了耐薯。
定義一個數(shù)組int dp[1000][50]={0}; dp[x][y]代表在1-y的y個數(shù)里面取數(shù)舔清，總和是x的情況有dp[x][y]種
用函數(shù)F(i,j)來求dp[i][j]，求出來的每個dp[i][j]記錄下來曲初，如果之前求過就不需要再繼續(xù)求
函數(shù)F分為4種情況
1.dp[i][j]已經(jīng)求出体谒，直接返回即可
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的時候抒痒，無數(shù)可取，返回0
4.i為0的時候颁褂，說明剛好取夠故响，此時dp[i][j]=1，返回1
最后實現(xiàn)的時候痢虹，運行超時被去，說明這個方法還有待改進，等下次有空再發(fā)新的
優(yōu)化后版本計蒜客 等和的分隔子集(優(yōu)化)
代碼
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;}
