Here is an instruction of this program: A board has n * m cells, and there is a
ID: 3837911 • Letter: H
Question
Here is an instruction of this program: 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 or diagonal in each step, and finally reach the cell at the bottom-right cell. The objective is to find the maximum total gifts you may earn and to find a route that generates the maximum. Use the dynamic programming to model, program this problem, and compute its time complexity. Test your program using several data sets generated by a random number generator .
*** I have a function that does find the maximum total gifts but I don't know how to find a route that generates the maximum. Can anyone help me adding some code to this function??? Thanks in advance.
public static void 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];
System.out.println("Max Value is " + maxValues[cols - 1]);
}
}
Explanation / Answer
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];
}