**: A board has**

__Question__*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.

**: It is a typical problem about dynamic programming. Firstly let’s analyze it with recursion. A function**

__Analysis__*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.

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.

This comment has been removed by the author.

ReplyDeleteCan this be solved using single loop?

ReplyDeleteGroovy 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"

}

Hi Jeesmon Jacob,

DeleteWhat 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.

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

ReplyDeleteGood suggestion. Your solution should work.

DeleteThis comment has been removed by the author.

ReplyDeletehow about if replace 6 by 1000? we missed the biggest giff?

ReplyDeleteThis is a bottom up approach, 1000 would be selected.

Deletehere 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);

}

System.out.println(maxgifts(new int[][] {

Delete{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.

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

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

ReplyDelete