Optimum Grid Harvest
by Isai Damier

/*********************************************************************
 * Author: Isai Damier
 * Title:  Optimum Grid Harvest
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given n boxes of avocados tightly arranged in a h*w grid, and given
 *   that you may only move down or to the right, amass the maximum
 *   number of avocados.
 *
 * Time-complexity: O(n)
 * 
 * Dynamic Programming Strategy:
 * 
 *   As it turns out this problem is easily solved by considering one
 *   box of avocado at a time. For each box of avocado: look up, look left,
 *   then pick the box that has more avocados and add it to the box on
 *   which you are standing.
 * 
 *   Here is how you might go about it:
 *   0] Think of the boxes of avocados as an A[1..h][1..w] matrix or array.
 *   1] Take a sheet of paper and draw an h*w grid on it. Say V[1..h][1..w].
 *   2] In the upper-left cell, V[0][0], write the number of avocados
 *      that's in the corresponding box: so V[0][0] = A[0][0]. This is
 *      because at A[0][0] there is nothing to the left or above. Simple.
 *   3] Imagine you took your next step to the right, then after looking
 *      up and looking left, you would have all the avocados in A[0][0]
 *      plus those in A[0][1]. Hence, cell V[0][1] would have
 *      V[0][0]+A[0][1] avocados. Again there is if you look up.
 *   4] But if instead of going right you went down, then after looking
 *      up and looking left, you would have all the avocados in A[0][0]
 *      plus those in A[1][0]. So that cell V[1][0] would have
 *      V[0][0]+A[0][1] avocados. (there is if you look left.)
 *   5] After filling each new cell on your sheet of paper, you can fill
 *      the next cell by evaluating the same possibilities as in step 3
 *      and step 4. So your overall process is
 *  
 *      V[i][j]=A[i][j] + max(V[i-1][j],V[i][j-1])
 * 
 *   6] When you are done with cell V[h][w], it will have the maximum
 *      number of avocados you can amass.
 * 
 * Of course in a real implementation, unless you are told not to modify
 * the input array A[1..h][1..w] you can double it as V[1..h][1..w]. In
 * this implementation, we assume we should not touch the original.
 * 
 * DETAILS YOU MAY NOT CARE FOR:
 * 
 * You could summarize the strategy above as follows:
 * 
 *   For each box we consider, we actually calculate the optimum solution
 *   up to that box. Further, to calculate the next box, we use the
 *   solutions for the previous boxes. So really we start with a small
 *   grid and then keep solving for larger and larger grids until we
 *   reach the final answer. Hence, we say the problem shows Optimal
 *   Substructures: each smaller segment of the grid is a grid, and the
 *   optimal solution to a smaller grid can be applied for solving a
 *   larger grid.
 * 
 *   Additionally, the grids overlap. What we mean is the grid
 *   A[1..i][1..j] is contained in A[1..i][1..j+1] which in turn is
 *   contained in A[1..i+1][1..j+1] up until A[1..h][1..w]. Hence,
 *   some of the smaller grids are actually completely parts of the
 *   larger grids. This trait is referred to as Overlapping Subproblems.
 * 
 *   Consequently, although we already knew that our strategy is
 *   Dynamic Programming, we can confirm that indeed it is Dynamic
 *   Programming since we used a table (i.e. V[1..h][1..w]) to solve
 *   a problem that exhibits both optimal substructures and overlapping
 *   subproblems. You may also hear the word memoize, which basically
 *   means we use V[1..h][1..w] to write down memos about each subproblem
 *   we solve.
 **********************************************************************/ 
 public int gridHarvest(int[][] grid) {
  if (null == grid) {
    return 0;
  }

  int[][] value = new int[grid.length][grid[0].length];
  int xMax = grid.length - 1;
  int yMax = grid[0].length - 1;
  for (int x = 0; x <= xMax; x++) {
    for (int y = 0; y <= yMax; y++) {
      amass(grid, x, y, value);
    }
  }
  return value[xMax][yMax];
}

private void amass(int[][] grid, int x, int y, int[][] value) {
  if (0 < x && 0 < y) {
    value[x][y] = grid[x][y] + Math.max(value[x - 1][y], value[x][y - 1]);
  } else if (0 < x) {
    value[x][y] = grid[x][y] + value[x - 1][y];
  } else if (0 < y) {
    value[x][y] = grid[x][y] + value[x][y - 1];
  } else {
    value[x][y] = grid[x][y];
  }
}
package algorithm.programming.dynamic;

import java.util.Arrays;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

public class HarvestingTest {

  /**
   * Test of gridHarvest method, of class Harvesting.
   */
  @Test
  public void testGridHarvest() {
    System.out.println("gridHarvest");
    int[][] grid = {
      {51, 42, 33, 25, 18},
      {13, 21, 34, 55, 89},
      {82, 63, 45, 27, 11},
      {13, 17, 19, 23, 29}
    };
    Harvesting instance = new Harvesting();
    int expResult = 344;
    int result = instance.gridHarvest(grid);
    assertEquals(expResult, result);
  }
  
  /**
   * Test of gridHarvest method, of class Harvesting.
   */
  @Test
  public void testGridHarvest7() {
    System.out.println("gridHarvest");
    int[][] grid = {
      {51, 92, 93, 97, 98},
      {13, 21, 34, 55, 89},
      {82, 63, 45, 27, 11},
      {13, 17, 19, 23, 29}
    };
    Harvesting instance = new Harvesting();
    int expResult = 560;
    int result = instance.gridHarvest(grid);
    assertEquals(expResult, result);
  }

  /**
   * Test of gridHarvest method, of class Harvesting.
   */
  @Test
  public void testGridHarvestL() {
    System.out.println("gridHarvest");
    int[][] grid = {
      {51, 42, 33, 25, 18},
      {93, 21, 34, 55, 89},
      {92, 63, 45, 17, 11},
      {93, 67, 59, 23, 29}
    };
    Harvesting instance = new Harvesting();
    int expResult = 507;
    int result = instance.gridHarvest(grid);
    assertEquals(expResult, result);
  }
}