Data Structures, Algorithms, & Applications in Java
Chapter 54, Exercise 2

First, we handle a few special cases. When the number of components is zero, the folding is possible regardless of the value of W; when we have one or more components, the folding cannot be done when W < w; and when n = 1 and W >= w, there are no fold points possible. All other cases as handled by computing the H values.

First, the Hi,1 and Hn,j values are computed. Next, Equation 54.2 is be used to compute the remaining Hi,js. The computation order is i = n-1, n-2, ..., 1. For each i, the order for the js is 2, 3, 4, ... s. For each Hi,j, we try values of k in the order i, i+1, ..., n-1.

The code is given below. 
public class EqualWidthFolding2
{
   /** fold components with heights h[1 .. h.length - 1] into a
     * rectangle of width theWidth
     * @param w is width of each component
     * @param r is array of space to be left at column ends
     * @param theH[i][j] is H_(i,j)
     * values of theH[1..h.length - 1][1..theWidth/w] and
     * kay[1..h.length-1][1..theWidth/w] are computed by this method
     * @return true iff the folding is possible */
   public static boolean equalWidthFolding(int [] h, int [] r, int w,
                                   int theWidth, int [][] theH, int [][] kay)
   {
      int n = h.length - 1;  // number of components
      int s = theWidth / w;  // max number of stacks
      if (n < 1)
         return true;
      if (s < 1)
         return false;
      if (n < 2)
         return true;

      // set boundary values of theH
      int hsum = 0;
      for (int i = n; i > 0; i--)
      {
         hsum += h[i];
         theH[i][1] = hsum + r[i];
      }
      for (int j = 1; j <= s; j++)
         theH[n][j] = h[n] + r[n];

      // compute remaining values using Eq. 54.4
      for (int i = n - 1; i > 0; i--)
         for (int j = 2; j <= s; j++)
         {
            hsum = 0;
            int minH = theH[1][1];   // upper bound
            int theK = 0;
            for (int k = i; k < n; k++)
            {
               hsum += h[k];
               int maxTerm = Math.max(hsum + r[i] + r[k + 1],
                                      theH[k + 1][j - 1]);
               if (maxTerm < minH)
               {
                  minH = maxTerm;
                  theK = k;
               }
            }   
            theH[i][j] = minH;
            kay[i][j] = theK;
         }
      return true;
   }
   
   /** output fold points */
   public static void traceback(int [][] kay, int theWidth, int w)
   {
      int n = kay.length - 1;   // number of components
      int s = theWidth / w;     // max number of stacks
   
      // find first nonzero kay[1][], this is also the number of stacks
      int j;
      for (j = s; j > 1; j--)
         if (kay[1][j] > 0)
            break;

      if (j < 2 || n < 2)
         System.out.println("There are no fold points");
      else
      {// there is at least one fold point
         System.out.print("The fold points are ");
         int i = 1;
         while (j > 1)
         {
            i = kay[i][j] + 1;
            System.out.print(i + " ");
            j--;
         }
         System.out.println();
      }
   }
}