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.

29 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
  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
  15. Using C++11 and recursion you can do:

    #include
    #include
    #include

    void findMaxValue(const std::vector > &matrix,
    int value, int row, int col,
    std::shared_ptr &max_value)
    {
    value += matrix[row][col];
    if (col < matrix[0].size() - 1)
    findMaxValue(matrix, value, row, col + 1, max_value);
    if (row < matrix.size() - 1)
    findMaxValue(matrix, value, row + 1, col, max_value);

    if (value > *max_value)
    *max_value = value;

    return;
    }

    int main()
    {
    std::vector > matrix = {{1, 10, 3, 8},
    {12, 2, 9, 6},
    {5, 7, 4, 11},
    {3, 7, 16, 5}};
    int value = 0, row = 0, col = 0;
    std::shared_ptr max_value(std::make_shared(0));
    findMaxValue(matrix, value, row, col, max_value);

    std::cout << "Max value is " << *max_value << std::endl;
    }

    ReplyDelete
  16. 16. Howdy Mate,



    Your writing shines like gold! There is no room for gibberish here clearly. You nailed it in #topic!



    I need something where I can run iis, sql server express and an application server to deploy a program. I thought I could use lightsail but I don't see an option to install the application server. Should I be using something else?



    Anyways great write up, your efforts are much appreciated.


    Best Regards,

    ReplyDelete
  17. Bonjour,


    I am shocked, shocked, that there is such article exist!! But I really think you did a great job highlighting some of the key #topic in the entire space.

    I started using this AWS Training blog for my training practice.

    We were experimenting with AWS and somehow linked existing accounts. If I click the button to say close account then I get a message stating:


    I look forward to see your next updates.


    Merci
    Morgan

    ReplyDelete
  18. Aloha,

    Maximal Value of Gifts being contrived to exist for many projects simply so it can be run will be the first to hit the wall, but those projects where the functions to make existing transactions cheaper in real world applications will find the elusive real world demand.




    A few months ago I shut everything down in AWS. I didn't close the account because I wanted to spin some things back up down the road when I had the time. A month later, I got a final bill for services that had been running mid-month when I closed them. Being somewhat Type A, I went into the Billing Console to review the charges and confirm what they were. Should have been the end of the story.

    I started using this AWS Training blog for my training practice.
    I read multiple articles and watched many videos about how to use this tool - and was still confused! Your instructions were easy to understand and made the process simple.


    Cheers,
    morgan

    ReplyDelete
  19. Ni Hau,

    Hot! That was HOT! Glued to the No. 56 - Maximal Value of Gifts your proficiency and style!


    I have to login to AWS multiple times a day but usually from the same desktop and browser. Since activating MFA, it has been a nightmare! At least twice a day I have to enter the MFA code from the authenticator. Even though I use the same browser! AWS Tutorial


    But nice Article Mate! Great Information! Keep up the good work!

    Many Thanks,
    Radhey

    ReplyDelete
  20. Through your pen I found the problem up interesting! I believe there are many other people who are interested in them just like me! How long does it take to complete this article? I hope you continue to have such quality articles to share with everyone! I believe a lot of people will be surprised to read this article! Thanks for your post!
    - gta 5 cheats

    ReplyDelete
  21. Coding

    Holiday Camps - We provide the best online learning coaching for Stem Education Coding in Singapore. Get the best online Stem Education Coding for your kids.

    https://www.bricks4kidz.com.sg/

    ReplyDelete
  22. خدمة كتابة السيرة الذاتية الإحترافية says
    Where to find best jobs in the world why not visit our website for jobs in saudi arabia other than saudi arabia you can look for jobs in pakistan and where you feel your cv is not professional feel free to use our Professional resume writing services we are here to help you out there in a world where completion is moving fast

    ReplyDelete