A board has n*m cells, and each cell has a value (positive or negative). The game is to start 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 values 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 used a max sum path, but i'm struggling to correctly read diagonally. I was wondering if you can help with that. Thank you.
public class game
{
static int matrixGame(int[][] a, int n, int m)
{
if(n == 1)
return a[0][0];
int b[][] = new int[n+1][m+1];
int max = Integer. MIN_VALUE, maxi;
for(int k = 0; k < n; k++) {
b[n - 1][k] = a[n - 1][k];
}
for (int i = n-2; i >= 0; i--)
{
for (int j = 0; j < n; j++)
{
maxi = Integer. MIN_VALUE;
if (((j - 1) >= 0) && (maxi < b[i+1][j-1]))
maxi = b[i+1][j-1];
if(((j+1) < n) && (maxi < b[i+1][j+1]))
{
maxi = b[i+1][j+1];
}
b[i][j] = a[i][j] + maxi;
}
}
for(int i = 1; i <= n;i++)
for(int j = 1; j <= m; j++)
{
if (max < b[i][j])
{
b[i][j] = Math. max(Math. max(b[i-1][j - 1], b[i-1][j]), b[i-1][j] + a[i-1][j]);
max = b[i][j];
}
}
return max;
}
}
java. util. Arrays;
import java. util.*;
public class main {
public static void main(String[] args) {
Scanner input = new Scanner(System. in);
System. out. println("Please enter the dimensions of your matrices");
System. out. print("Rows: ");
int inputRow = input. nextInt();
System. out. print("Columns: ");
int inputCol = input. nextInt();
System. out. println("Please enter the values for matrix: ");
int[][] matrixOne;
matrixOne = new int[inputRow][inputCol];
for (int row = 0; row < inputRow; row++) {
for (int col = 0; col < inputCol; col++) {
matrixOne[row][col] = input. nextInt();
}
}
System. out. println("Matrix: ");
for (int i = 0; i < matrixOne. length; i++) {
for (int j = 0; j < matrixOne[i].length; j++) {
System. out. print(matrixOne[i][j] + " ");
}
System. out. println();
}
System. out. println();
int m = matrixOne. length;
int n = matrixOne. length;
System. out. print(game. matrixGame(matrixOne, n,m));
}
}