USACO中的动态规划问题

Question

在2.2节,一个名为"子集和"的问题需要你来计算多少种方式可以设置从1到n的整数被分成两组,其金额是相同的.

我知道复发是:

f [i] [j]:用1 ... i总结j的方法的数量

F [i] [j] = F [I-1] [j] + F [I-1] [ジ]

如果初始条件是:

f [1] [1] = 1; //其他都为零,主循环从2开始

要么:

f [0] [0] = 1; //其他都为零,主循环从1开始

答案都是f [n] [n*(n + 1)/ 4].这是否意味着初始条件不会影响答案？

但如果我使用一维数组,请说f [N]:

令f [0] = 1,从1循环(所以f [0]实际上是f [0] [0]),答案是f [n]/2

或f [1] = 1,从2循环(f [1]为f [1] [1]),答案为f [n]

我感到很困惑...

Answer 1

我不知道你是否仍然坚持这个问题,但对于遇到这个问题的其他人来说,这是一个解决方案.

让方法[i]是你可以使用数字1 ... N的子集得到i的总和的方式的数量.

然后它成为0-1背包算法的变体:

基本情况:方式[0] = 1

for (int i = 1; i <= N; i++) {
    for (int j = sum - i; j >= 0; --j) { //sum is n*(n+1)/2
        ways[j + i] += ways[j];
    }
}

您的答案位于[sum/2]/2.