dynamic-programming - USACO 中的一个动态规划问题

Question

section2.2中的“子集和”问题要求你计算从1到n的整数集合有多少种方式可以分成两个和相同的集合。

我知道重现是:

f[i][j] : numbers of ways that sum up to j with 1...i

f[i][j]=f[i-1][j]+f[i-1][j-i]

如果初始条件是:

f[1][1]=1;//others are all zero,main loop start from 2

或者:

f[0][0]=1;//others are all zero,main loop start from 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

我不知道您是否仍然被这个问题所困扰，但这里有一个解决方案供其他遇到此问题的人使用。

设 ways[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];
    }
}

您的答案位于 ways[sum/2]/2。