Calculating the number of tetrahedrals required to represent an integer in Java using dynamic programming

Computing all the tetrahedral numbers that are smaller than the given threshold:

public static Integer[] computeTetrahedralNumbers(double limit){

    List tetraNumList = new ArrayList();

    int i = 1;

    int tetra_N = 0;

    while (tetra_N <= limit){
        int tri_N = 0, n;

        tetra_N = 0;

        for (n = 1; n <= i; n++) {
            tri_N += n;

            tetra_N += tri_N;

        }

        if(tetra_N <= limit){
            tetraNumList.add(tetra_N);

        }

        i++;

    }

    return tetraNumList.toArray(new Integer[tetraNumList.size()]);

}

Initializing the arrays:

Integer[] tetrahedrals = computeTetrahedralNumbers(n);

/**

* Each cell C[i,j] equals to the number of tetrahedrals required to represent

* the integer j,taking into consideration the tetrahedrals from the

* first till the i-th.

*/

C = new int[tetrahedrals.length][n+1];

for(int i = 0; i    C[i][0] = 0;

}

/**

* Each cell of the first row is initialized with the value of its

* column since 1 is a tetrahedral and so each integer can be

* represented by a sum of ones.

*/

for (int j = 1; j < n+1; j++) {
    C[0][j]=j;

}

Calculating the number of tetrahedrals required to represent an integer:

/**

* Utilizes the array C from the first column till the n-th.

* Each utilized cell is either assigned the value of the cell above it (when

* the integer it represents is smaller than the maximum tetrahedral that can

* be used-since that tetrahedral obviously cant be taken into consideration

* because the result would be bigger than the target) or the minimum value

* between the cell above it and the number of tetrahedrals required to

* represent the integer n-(maximum allowed tetrahedral) plus one (so the maximum

* allowed tetrahedral is taken into consideration).

*

* When the method is finished,the first n+1 cells of the last row contain

* the minimum number of tetrahedrals required to represent the integers from 0 to n

* and the first n+1 columns contain the process done for that calculation.

*

* If n=number of tetrahedrals smaller than the limit and W=number of integers

* the time and space complexity is pseudo-polynomial-O(nW).The number of integers

* (10000) can be represented with 14 bits and if it gets doubled,15 bits will be

* needed whereas the number of operations will be at least doubled(since an

* increase at the number of integers also increases the available tetrahedrals)

* so when the input is increased by one bit,the complexity is exponential

* if the input is seen as bits and pseudo-polynomial if seen as number.If

* the number of tetrahedrals is doubled,the array will have doubled amount of

* rows(double the space) and the number of operations will be doubled too,

* so complexity will be considered polynomial.

*

*

* @param n

* @return the number of tetrahedrals required to represent n

*/



public int computeTetrahedralSumCount(int n) {

    for (int i = 1; i < C.length; i++) {
        for (int j = 1; j <= n; j++) {
//could be avoided under the

//assumption that the method has been called for all the integers

//before the n-th and the array is already correct till the n-th

//column and set j=n without looping

            if(j                C[i][j]=C[i-1][j];

            }else{

                C[i][j]=Math.min(C[i-1][j], 1+C[i][j-tetrahedrals[i]]);

            }

        }

    }

    return C[C.length-1][n];

}