Saturday, October 4, 2014

No. 56 - Maximal Value of Gifts


Question: A board has n*m cells, and there is a gift with some value (value is greater than 0) in every cell. You can get gifts starting from the top-left cell, and move right or down in each step, and finally reach the cell at the bottom-right cell. What’s the maximal value of gifts you can get from the board?

For example, the maximal value of gift from the board above is 53, and the path is highlighted in red.

Analysis: It is a typical problem about dynamic programming. Firstly let’s analyze it with recursion. A function f(i, j) is defined for the maximal value of gifts when reaching the cell (i, j). There are two possible cells before the cell (i, j) is reached: One is (i - 1, j), and the other is the cell (i, j-1). Therefore, f(i, j)= max(f(i-1, j), f(i, j-1)) + gift[i, j].

Even though it’s a recursive equation, it’s not a good idea to write code in recursion, because there might be many over-lapping sub-problems. A better solution is to solve is with iteration. A 2-D matrix is utilized, and the value in each cell (i, j) is the maximal value of gift when reaching the cell (i, j) on the board.

The iterative solution can be implemented in the following Java code:
public static int getMaxValue(int[][] values) {
    int rows = values.length;
    int cols = values[0].length;
    int[][] maxValues = new int[rows][cols];

    for(int i = 0; i < rows; ++i) {
        for(int j = 0; j < cols; ++j) {
            int left = 0;
            int up = 0;

            if(i > 0) {
                up = maxValues[i - 1][j];
            }

            if(j > 0) {
                left = maxValues[i][j - 1];
            }

            maxValues[i][j] = Math.max(left, up) + values[i][j];
        }
    }

    return maxValues[rows - 1][cols - 1];
}

Optimization

The maximal value of gifts when reaching the cell (i, j) depends on the cells (i-1, j) and (i, j-1) only, so it is not necessary to save the value of the cells in the rows i-2 and above. Therefore, we can replace the 2-D matrix with an array, as the following code shows:

public static int getMaxValue(int[][] values) {
    int rows = values.length;
    int cols = values[0].length;

    int[] maxValues = new int[cols];
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            int left = 0;
            int up = 0;

            if (i > 0) {
                up = maxValues[j];
            }

            if (j > 0) {
                left = maxValues[j - 1];
            }

            maxValues[j] = Math.max(left, up) + values[i][j];
        }
    }

    return maxValues[cols - 1];
}

The source code with unit test cases is shared at http://ideone.com/2vLRMk.
More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact the author via zhedahht@gmail.com . Thanks.

18 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Can this be solved using single loop?

    Groovy ex:

    def cc59() {
    int[][] m = [
    [1, 10, 3, 8],
    [12, 2, 9, 6],
    [5, 7, 4, 11],
    [3, 7, 16, 5]
    ]

    int rows = m.length
    int cols = m[0].length

    int sum = m[0][0]

    println m[0][0]

    int i, j = 0

    while(i + 1 < rows || j + 1 < cols) {
    if(i + 1 < rows && m[i+1][j] > m[i][j+1]) {
    println m[i+1][j]
    sum += m[++i][j]
    }
    else {
    println m[i][j+1]
    sum += m[i][++j]
    }
    }

    println "sum: $sum"
    }

    ReplyDelete
    Replies
    1. Hi Jeesmon Jacob,
      What is complexity of this program which you made ???
      I am always confused when things come for complexity, it would be great if you will make me understand, thanks in advance.

      Delete
  3. I would try to map the matrix to a single sourced graph with the values being the weight of the paths, then find the longest path to destination using Dijkstra's algorithm

    ReplyDelete
    Replies
    1. Good suggestion. Your solution should work.

      Delete
  4. This comment has been removed by the author.

    ReplyDelete
  5. how about if replace 6 by 1000? we missed the biggest giff?

    ReplyDelete
    Replies
    1. This is a bottom up approach, 1000 would be selected.
      here my DP attempt


      public static class Coord {
      final int row;
      final int col;
      // limited to 10 * 10
      private final static Coord[] cache = new Coord[1 << 19];
      public Coord(int row, int col) {
      this.row = row;
      this.col = col;
      }

      @Override
      public boolean equals(Object obj) {
      Coord o = (Coord) obj;
      return this.row == o.row && this.col == o.col ;
      }

      @Override
      public int hashCode() {
      return (row << 15) + col;
      }
      static Coord forValues(int row, int col) {
      int key = (row << 15) + col;
      if (cache[key] != null) {
      return cache[key];
      }
      cache[key] = new Coord(row, col);
      return cache[key];
      }

      @Override
      public String toString() {
      List l = Arrays.asList(row, col);
      return l.toString();
      }
      }

      public static List maxgifts(int[][] matrix) {
      Map> cache = new HashMap<>();
      return traverseMatrix(matrix, 0, 0, cache);
      }

      private static List traverseMatrix(int[][] matrix, int row, int col, Map> cache) {
      Coord cacheKey = Coord.forValues(row, col);
      if (cache.containsKey(cacheKey)) {
      return cache.get(cacheKey);
      }

      if (row == matrix.length || col == matrix[0].length) {
      return new LinkedList<>();
      }

      List right = new LinkedList<>();
      List down = new LinkedList<>();

      right.addAll(traverseMatrix(matrix, row, col + 1, cache));
      down.addAll(traverseMatrix(matrix, row + 1, col, cache));

      int sumDown = down.stream().mapToInt(coord -> (Integer) matrix[coord.row][coord.col]).sum();
      int sumRight = right.stream().mapToInt(coord -> (Integer) matrix[coord.row][coord.col]).sum();

      cache.put(cacheKey, sumDown > sumRight ? down : right);
      cache.get(cacheKey).add(cacheKey);

      return cache.get(cacheKey);
      }

      Delete
    2. System.out.println(maxgifts(new int[][] {
      {1, 10, 3, 8, 15},
      {12, 2, 9, 1000, 10},
      {5, 7, 4, 11, 1},
      {3, 7, 16, 5, 8},
      {30, 70, 1, 50, 8}}));

      outputs:[[4, 4], [4, 3], [3, 3], [2, 3], [1, 3], [1, 2], [1, 1], [1, 0], [0, 0]]

      Note that I replace 6 by 1000 and added a col. in original matrix, the red path is reproduced.

      Delete
  6. Thanks for sharing this information. I really like your blog post very much. You have really shared a informative and interesting blog post with people.. custom bobbleheads

    ReplyDelete
  7. Excellent post <a href="http://interviewwale.blogspot.com> really helpful </a>

    ReplyDelete
  8. Its just a remarkable post.If you wants to get best technical writing then must visit our blog! technical report writing

    ReplyDelete
  9. Though online MBA degree is nothing new, yet these are still some common problems and mistakes faced by the online MBA Degree students. Do not enroll in any unaccredited school as its degree may not be accepted by other universities/schools or even the future employers.proposal writing services

    ReplyDelete
  10. Invest more energy in perusing quality books to enhance your insight instead of appreciating your magnificence. Since one day your magnificence will vanish and you would be left with the measure of learning you picked up.good site

    ReplyDelete
  11. This comment has been removed by the author.

    ReplyDelete
  12. Boston is that the Hub for each if you're drawing near business or for vacation, you want to relish some time here, as its residents referred to as it as company or the Business center. If you want to urge around this mentioned place, continually victimization the cab service is kind of problem. best corporate brochure design

    ReplyDelete
  13. writing a imitate profile it comes to getting professional company profile writing help, we are detached to declaration we are the industry leading experts to direction to for strive for. At our company profile company, we anxiety to present our clients taking into consideration the powerful, professional company profile services that they are looking for, at prices that wont crack the bank. To know about professional ghostwriters

    ReplyDelete
  14. The best way to learn the coding or programming is just by practisizing the program on the compiler. If the company hire the person for the job of programmer then they just check the level of programming skill. Programming is not scary like best ghostwriters for hire and bad dreams. It's your duty to write the code again and again with different logicical analysis to learn more better.

    ReplyDelete