Project Euler 76 - Counting Summations

Posted on December 9, 2013

Last updated on December 10, 2013

We can use a dynamic programming bottom-up approach.

public class Euler76 {
  public int intPartition(int n){
    /*
     * N[i][j] is the number of ways to partition i using
     * integers from 1 to j inclusive.
     * 
     * N[i][j] = N[i-1][j]     +    N[i-j][j]
     *           (j not used)       (j used)
     */

    int N[][] = new int [n+1][n+1];
    for(int i = 0; i <= n; i++){
      N[0][i] = 1;
    }
    
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= n; j++){
        if(j > i) N[i][j] = N[i][j-1];
        else N[i][j] = N[i][j-1] + N[i-j][j];
      }
    }   
    
    return N[n][n-1];
  }
  
  public static void main(String[] args) {
    System.out.println(new Euler76().intPartition(100));
  }
}
Project Euler 76
Markdown SHA1: c4c22dae97d89de679c4477cbc35c76f92817895