本文共 850 字,大约阅读时间需要 2 分钟。
对于由从1到N (1 <= N <= 39)这N个连续的整数组成的集合来说,我们有时可以将集合分成两个部分和相同的子集合。
例如,N=3时,可以将集合{1, 2, 3} 分为{1,2}和{3}。此时称有一种方式(即与顺序无关)。
N=7时,共有四种方式可以将集合{1, 2, 3, ..., 7} 分为两个部分和相同的子集合:
{1,6,7} 和 {2,3,4,5}
{2,5,7} 和 {1,3,4,6}
{3,4,7} 和 {1,2,5,6}
{1,2,4,7} 和 {3,5,6}
输入:程序从标准输入读入数据,只有一组测试用例。如上所述的N。
输出:方式数。若不存在这样的拆分,则输出0。
dp[7]=1+dp[6]+2+dp[5]+3+dp[4]+4+dp[3]+5+dp[2]+6+dp[1];
dp[6]=1+dp[5]+2+dp[4]+3+dp[3]+4+dp[2]+5+dp[1];
······
dp[0]=1;只有一种方式——————————个人觉得这种描述方式最简单,刚看见一片繁琐的解释如下:
http://www.cnblogs.com/kangjianwei101/p/5332451.html
#include"stdio.h"#include"string.h"int main(){ int n,i,j,sum; long dp[1000]; memset(dp,0,sizeof(dp));//将数组初始化 dp[0]=1; scanf("%d",&n); sum=n*(n+1); if (sum%4) {printf("0\n");return 0;} else { sum=sum/4; for(i=1;i<=n;i++) for(j=sum;j>=i;j--) dp[j]+=dp[j-i]; } printf("%d\n",dp[sum]/2);}
其实还有一个问题,为什么定义为dp[100]的时候就无效内存引用,求大神解释