A Dynamic Programming problem in USACO

In section2.2,a problem called"subset sum"require you to calculate in how many ways can a integer set from 1 to n be partitioned into two sets whose sums are identical.

I know the recurrence is:

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]

if the initial condition is:

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

OR:

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

the answers are all f[n][n*(n+1)/4].Does this means the initial condition doesn't affect the answer?

but if I use a one dimension array,say f[N]:

let f[0]=1,loop from 1(so f[0] is f[0][0] in fact),the answer is f[n]/2

or f[1]=1,loop from 2(f[1] is f[1][1]),the answer is f[n]

I am so confused...

I don't know if you are still stuck on this problem, but here's a solution for anyone else who stumbles onto this problem.

Let ways[i] be the number of ways you can get a sum of i using a subset of the numbers 1...N.

Then it becomes a variant of the 0-1 knapsack algorithm:

base case: ways[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];
    }
}

Your answer is located at ways[sum/2]/2.