Collecting Apples

Problem: The original problem is from TopCoder. Given a M*N matrix, in each cell, there are a number of apples. When you visit one cell, you can grab the apple away. You make three passes to collect apples. In the first pass, you start from top-left,  go either right or down until reading bottom-right. In the second pass, you start from bottom-right, go either up or left until reading top-left. In the third pass, you go from top-left to bottom-right again. What are the maximum number of apples you can collect?

Solution: This is a DP problem. But first we need to do some reduction to convert the problem to a easier one. If the problem only contains the first pass, it is an easy DP problem.

• One key observation is the second pass can be reversed so that the problem can be transferred to that three paths starting from top-left to bottom-right.
• We create a status matrix MAX[][][], MAX[i][j][k] denote at a certain round, the column coordinates of the three paths (you can get the row coordinates from i,j,k and round number x). 
• From the previous position to current position, at most three cells should be visited. They are (x-i, i), (x-j, j) and (x-k, k). Then we can get the apples at the three cells (remember don't add the duplicate cell). There are multiple ways (2*2*2) to reach these three cells (from up or from left). They we need to leverage the MAX[][][] from previous round to find a previous state to the three cells which can maximize MAX[i][j][k]. 
• There are totally M+N-2 rounds and after the final round, the answer will be stored in MAX[N-1][N-1][N-1]

The key algorithm is as follow:

public int mostApples(string[] L) {

    int X=L[0].Length, Y=L.Length, XY=X+Y;
    int[,,] best = new int[X,X,X]; 
    int[,,] b2 = new int[X,X,X];     
     
    for (int A=0; A<X; A++) 
    for (int B=0; B<X; B++) 
    for (int C=0; C<X; C++)    
        best[A,B,C] = -999999999;

    best[0,0,0] = 0;

    for (int t=1; t<=X+Y-2; t++)
    {    
        for (int A=0; A<X; A++) 
        for (int B=0; B<X; B++) 
        for (int C=0; C<X; C++)
        {
           int aa = t-A, bb=t-B, cc=t-C;
           if (aa < 0 || bb < 0 || cc < 0 || aa >= Y || bb >= Y || cc >= Y) continue;
  
           int bestHere = 0;
           int delta = (int)(L[aa][A] - 48);
           
           if (B != A) delta += (int)(L[bb][B] - 48);
           if (C != A && C != B) delta += (int)(L[cc][C] - 48);
 
           if ( A>0 &&  B>0 &&  C>0) bestHere = Max(bestHere, best[A-1, B-1, C-1] + delta);
           if ( A>0 &&  B>0 && cc>0) bestHere = Max(bestHere, best[A-1, B-1, C  ] + delta);
           if ( A>0 && bb>0 &&  C>0) bestHere = Max(bestHere, best[A-1, B,   C-1] + delta);
           if ( A>0 && bb>0 && cc>0) bestHere = Max(bestHere, best[A-1, B,   C  ] + delta);
           if (aa>0 &&  B>0 &&  C>0) bestHere = Max(bestHere, best[A,   B-1, C-1] + delta);
           if (aa>0 &&  B>0 && cc>0) bestHere = Max(bestHere, best[A,   B-1, C  ] + delta);
           if (aa>0 && bb>0 &&  C>0) bestHere = Max(bestHere, best[A,   B,   C-1] + delta);
           if (aa>0 && bb>0 && cc>0) bestHere = Max(bestHere, best[A,   B,   C  ] + delta);
           b2[A,B,C] = bestHere;
         }
 
         int[,,] temp = best; 
         best = b2; 
         b2 = temp;
  }
 
return best[X-1,X-1,X-1];
}