USACO：子集（低效）

Question

我正在尝试解决来自 USACO 培训网关的子集...

问题陈述

对于从 1 到 N (1 <= N <= 39) 的许多连续整数集合，可以对集合进行分区分成总和相同的两组。

例如，如果 N=3，则可以用一种方式划分集合 {1, 2, 3}，以便两个子集的总和相同：

{3} 和 {1,2} 这算作单个分区（即将顺序计数颠倒为相同的分区，因此不会增加分区的数量）。

如果 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，您的程序应该打印包含从 1 到 N 的整数的集合可以分为两个总和相同的集合的方式数。如果没有这样的方法则打印 0。

您的程序必须计算答案，而不是从表格中查找答案。

结束

在我通过简单地排列集合并求和来运行 O(N*2^N) 之前。

发现这是多么低效，我继续映射总和序列...... http://en.wikipedia.org/wiki/Composition_(number_theory)

经过多次编码问题来刮掉重复，仍然太慢，所以我回到了第一个:(。

现在我更仔细地研究了这个问题，看来我应该尝试找到一种方法来不求和，但实际上直接去到号码 如果有人能告诉我如何解决这个

问题，我会用 java、C++ 和 python 编程。

Answer 1

这与在多项式 (x^1+1/x)(x^2+1/x^2)...(x^n+1/x^n) 中查找系数 x^0 项是一样的，其上限约为 O(n^3)。

Answer 2

实际上，有更好、更简单的解决方案。您应该使用动态编程
反而。在您的代码中，您将有一个整数数组（其大小为总和），其中索引 i 处的每个值表示可能对数字进行分区的方法数，以便其中一个分区具有i 的总和。您的代码在 C++ 中可能如下所示：

int values[N];
int dp[sum+1]; //sum is the sum of the consecutive integers

int solve(){
    if(sum%2==1)
        return 0;
    dp[0]=1;
    for(int i=0; i<N; i++){
        int val = values[i]; //values contains the consecutive integers
        for(int j=sum-val; j>=0; j--){
            dp[j+val]+=dp[j];
        }
    }
    return dp[sum/2]/2;
}

这为您提供了一个 O(N^3) 解决方案，对于此问题而言，它的速度足够快。

我还没有测试过这段代码，所以可能存在语法错误或其他错误，但你明白了。如果您还有其他问题，请告诉我。