### Counting summations题号：76 难度： 10 中英对照

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

### Code

import java.math.*;

public final class p76 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
static public String run(){
return partitions(100, 1).subtract(BigInteger.ONE).toString();
}

private static BigInteger partitions(int n, int k) {
BigInteger[][] table = new BigInteger[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = n; j >= 0; j--) {
if (j == i)
table[i][j] = BigInteger.ONE;
else if (j > i)
table[i][j] = BigInteger.ZERO;
else if (j == 0)
table[i][j] = table[i][j + 1];
else
table[i][j] = table[i][j + 1].add(table[i - j][j]);
}
}
return table[n][k];
}

}
190569291
3ms