94.子集和 (10分)

C时间限制:1 毫秒 |  C内存限制:65535 Kb
题目内容:
 对于由从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。
输入样例
7
输出样例
4


 

思路:

这道题我开始只有一点思路,就是关于这个数加还是不加,想到dfs,但是又想到它无法记得我加了哪个数,无法实现,然后看了别人的博客

用动态规划,这个真的有点意思。

dp[i][sum] 中i代表的是i这个数,sum代表的是子集和的整数被限制为sum,然后从加还是不加i这个数进行分类

94.子集和 (10分)

 

1.如果i==0 ,sum==0,这里很关键,就是把0放入这个子集和为0 的集合中,方案数为1;

2.当i==0,sum>0,无法放入,所以方案数为0;

3.i>sum,就是说这个数大于这个被限制为数值为sum的子集和,所以无法放入,因此为dp[i-1][sum];

4.i<=sum,这里需要分类讨论,i这个数有资格放入这个集合中,但是可以放也可以不放,所以为dp[i-1][sum](不放的方案数)+dp[i-1][sum-i](放的方案数),dp[i-1][sum-i]含义:我们要把i这个数放入这个集合中,所以我们要预先就留i这么大的空间,所以我们只有数值为sum-i的子集和

 


 

 

代码:

#include<iostream>
#include<stdio.h>
using namespace std;
const int maxn = 2e3+10;
int dp[50][maxn];
int main(){
    int n;
    cin>>n;
    int sum;
    sum = (1+n)*n/2;
    if(sum%2==1)
        cout<<"0"<<endl;
    else{
        sum = sum/2;
        dp[0][0] = 1;
        for(int i=1;i<=n;i++)
            dp[0][i] = 0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=sum;j++){
                if(j<i)
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = dp[i-1][j]+dp[i-1][j-i];
            }
        }
        cout<<dp[n][sum]/2<<endl; 
    }
    return 0;
}

 

上一篇:LeetCode系列7:求最大子序和


下一篇:94. 二叉树的中序遍历