Today we continue with one more problem solving discussion. We look at  box stacking problem. We are given a set of n types of rectangular three dimensional boxes of length Li width WI and height hi . We have to stack the boxes so they for tallest tower. Each box must sit on top of a bigger or equal box and there can be many boxes of the same size. A rectangular box can be rotated so that it can lay on any of its faces.
This problem is similar to the previous increasing subsequence we have seen. We generates all the three base areas for a rectangle of a box. Then we sort them in increasing order. At this point, the pro lem is that of finding the longest common subsequence of height hi
Let MSH (i) be the  max height of the tower.
MSH (i) = max ( MSH (j) + height hi)  when w × l (j) is bigger and j < I and
If no such MSH (j) exists then MSH (i) = h (i)
This we can write as

for (int i = 1; i < n; i ++)

     for (int j = 0; j <i; j++)

         if (w (j)*l(j) > w (i)*l (i) && max (MSH (j) + h (i)) > msh (i)
                MSH (i) = max (MSH (j) + h (i))

To get the maximum overall stack height, we return the max (MSH (i)) where 0 < I < n

We now look at a problem that involves backtracking instead of dynamic programming.
Let us say we want to color the map of United States such that no two bordering states have the same color.  We are allowed to use four colors : red orange green and blue
Let us say we number the states say from  1 to 50 and we denote the current state with the number n
Let us say we consider each color for a state say denoted by c. If its' valid we choose the color and try to recursively find solutions applying that color for the n+1 going forward. If we found a solution applying this color or during the termination check when n == 50 then we return true. For backtracking, we remove the color and proceed with the next color as candidate. Finally we return false if we didn't find a solution using up all the available colors.

bool findColors(int n, Pair<int,color> states)
{
 if (n == 51) { 
    printColors();
    return true;
}
    foreach (color c in colors) {
      if (isValid(c,n)){
           states[n] = c; //apply color
           if (findColors(n+1, states))
              return true;
           states[n] = '/0';//remove color
        }
    }
  return false;
}
Back tracking never considers an invalid option and reduces the number of options from the permutations.