| 22 | } |
| 23 | |
| 24 | public static int solve (int n, int m, int grid[][], int dp[][][], int row1, |
| 25 | int col1, int row2) |
| 26 | { |
| 27 | int col2 = (row1 + col1) - (row2); |
| 28 | |
| 29 | if (row1 == n - 1 && col1 == m - 1 && row2 == n - 1 && col2 == m - 1) |
| 30 | return 0; |
| 31 | |
| 32 | if (row1 >= n || col1 >= m || row2 >= n || col2 >= m) |
| 33 | return -1 * Integer.MAX_VALUE; |
| 34 | |
| 35 | if (dp[row1][col1][row2] != -1) |
| 36 | return dp[row1][col1][row2]; |
| 37 | |
| 38 | int ch1 = -1 * Integer.MAX_VALUE, ch2 = -1 * Integer.MAX_VALUE; |
| 39 | int ch3 = -1 * Integer.MAX_VALUE, ch4 = -1 * Integer.MAX_VALUE; |
| 40 | |
| 41 | if (grid[row1][col1 + 1] != -1 && grid[row2 + 1][col2] != -1) |
| 42 | ch1 = |
| 43 | cost (grid, row1, col1 + 1, row2 + 1, col2) + solve (n, m, grid, dp, |
| 44 | row1, col1 + 1, |
| 45 | row2 + 1); |
| 46 | |
| 47 | if (grid[row1][col1 + 1] != -1 && grid[row2][col2 + 1] != -1) |
| 48 | ch2 = |
| 49 | cost (grid, row1, col1 + 1, row2, col2 + 1) + solve (n, m, grid, dp, |
| 50 | row1, col1 + 1, |
| 51 | row2); |
| 52 | |
| 53 | if (grid[row1 + 1][col1] != -1 && grid[row2][col2 + 1] != -1) |
| 54 | ch3 = |
| 55 | cost (grid, row1 + 1, col1, row2, col2 + 1) + solve (n, m, grid, dp, |
| 56 | row1 + 1, col1, |
| 57 | row2); |
| 58 | |
| 59 | if (grid[row1 + 1][col1] != -1 && grid[row2 + 1][col2] != -1) |
| 60 | ch4 = |
| 61 | cost (grid, row1 + 1, col1, row2 + 1, col2) + solve (n, m, grid, dp, |
| 62 | row1 + 1, col1, |
| 63 | row2 + 1); |
| 64 | |
| 65 | return dp[row1][col1][row2] = |
| 66 | Math.max (ch1, Math.max (ch2, Math.max (ch3, ch4))); |
| 67 | } |
| 68 | |
| 69 | public static void initializeDp (int dp[][][], int item) |
| 70 | { |