/**
 * Tower height dynamic programming example
 */

import java.lang.Math;
import java.lang.Integer;

public class TowerHeight
{
    // instance variables - replace the example below with your own
    static int[] blocks = {1, 10, 25};
    static int maxHeight = 50;

    public static void main(String[] args) 
    {
        // print out available blocks
        System.out.print("Available block lengths:");
        for (int i = 0; i < blocks.length; i++)
            System.out.print(" " + blocks[i]);
        System.out.println();
        
        // initialize the h array
        int[] h = new int[maxHeight];
        int[] lastBlock = new int[maxHeight];
        for (int i = 1; i < maxHeight; i++) {
            h[i] = 0;
            lastBlock[i] = -1;
        }

        // set up the base cases
        for (int i = 0; i < blocks.length; i++) {
           h[blocks[i]] = 1;
           lastBlock[blocks[i]] = i;
        }   
           
        for (int i = 1; i < maxHeight; i++)
        {
           if (h[i] == 0) // not a base case, so compute value
           {
               int minValue = Integer.MAX_VALUE;
               for (int j = 0; j < blocks.length; j++) 
               {
                   int blockLength = blocks[j];
                   int pos = i - blockLength;
                   if (pos > 0 && h[pos] > 0) // look in h[pos] for minimum value
                   {    
                       if (h[pos] < minValue)
                       {
                           minValue = h[pos];
                           lastBlock[i] = j;
                       }
                   }   
               }
               if (minValue != Integer.MAX_VALUE)
                   h[i] = minValue + 1;
           }
           if (h[i] > 0) {
               System.out.println("A tower of height " + i + " can be built with " + h[i] + " block(s).");
               System.out.print("Blocks used in solution: ");
               int remainingHeight = i;
               while (remainingHeight > 0) {                   
                   System.out.print(" " + blocks[lastBlock[remainingHeight]]);
                   remainingHeight -= blocks[lastBlock[remainingHeight]];
               }
               System.out.println();
           } else
               System.out.println("A tower of height " + i + " cannot be built from the blocks available.");
        }
    }
}