当前位置:首页 » Project Euler » 详细页

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?

Solution

动态规划。 设$table[i][j]$表示将数字$i$分解为不低于$j$的方法数。 那么$table[i][j]=0 \quad \forall i< j $,且$table[i][j]=1 \quad \forall i==j$,且$table[i][0]=table[i][1] \quad \forall i$。 递推公式为: $$table[i][j]=table[i][j+1]+table[i-j][j]$$

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