Maximum Coins Problem in Java
In this section, we will delve into the solution for the maximum coin problem in Java. Navigating a 2D grid from the top-left corner to the bottom-right corner is the challenge at hand. You can only go down or to the right at each phase. The objective is to identify the path that maximizes the total number of coins collected by adding up the values of the cells along the selected path. The grid contains cells that contain coins.Top of Form
Example 1:
Input:
Output: Maximum number of coins collected: 12
Explanation: Begin at (0, 0) and gather one coin.
Proceed to the right and stop at (0, 1) to gather 3 coins.
Go to location (1, 1) and gather 5 coins.
Proceed to location (2, 1) and gather two coins.
Go to position (2, 2) on the right, and pick up 1 coin.
These coin values add up to 1 + 3 + 5 + 2 + 1 = 12.
Approach: Using Recursion
The maxCoinsRecursive() method uses a recursive technique to determine the greatest amount of coins that can be obtained by navigating a two-dimensional grid. It considers advancing down or right, accumulating coins to the bottom-right corner, starting from the top-left corner. This loop is started recursively from the upper-left corner by the maxCoins() method.
FileName: MaximumCoins.java
public class MaximumCoins {
public static int maxCoinsRecursive(int[][] grid, int row, int col) {
int rows = grid.length;
int cols = grid[0].length;
// Base case: If current position is at the bottom-right corner
if (row == rows - 1 && col == cols - 1) {
return grid[row][col];
}
// If we reach the bottom or right edge, we can only move in one direction
if (row == rows - 1) {
return grid[row][col] + maxCoinsRecursive(grid, row, col + 1);
}
if (col == cols - 1) {
return grid[row][col] + maxCoinsRecursive(grid, row + 1, col);
}
// Recursive case: Move right or down and choose the maximum coins
int right = maxCoinsRecursive(grid, row, col + 1);
int down = maxCoinsRecursive(grid, row + 1, col);
return grid[row][col] + Math.max(right, down);
}
public static int maxCoins(int[][] grid) {
return maxCoinsRecursive(grid, 0, 0);
}
public static void main(String[] args) {
int[][] grid = {
{1, 3, 1},
{1, 5, 1},
{4, 2, 1}
};
System.out.println("Maximum number of coins collected: " + maxCoins(grid));
}
}
Output:
Maximum number of coins collected: 12
Complexity Analysis: The recursive method demonstrates an O(2^(m+n)) exponential time complexity, where 'm' denotes the number of rows and 'n' is the number of columns. The recursive method uses O(m + n) space for the recursive call stack in terms of space complexity.
Approach: Using Dynamic Programming
Step 1: Create a 2D DP table with dimensions: rows x cols.
Step 2: Initialize the bottom-right cell: dp[rows - 1][cols - 1] = grid[rows - 1][cols - 1].
Step 3: Initialize the last row and last column of the DP table:
Each cell in the final row is filled by adding the current grid value to the value on its right (dp[rows - 1][i] = grid[rows - 1][i] + dp[rows - 1][i + 1]), working from the second-to-last column to the first column.
For the last column, starting from the second-to-last row to the first row, each cell is filled by adding the current grid value to the value below it (dp[i][cols - 1] = grid[i][cols - 1] + dp[i + 1][cols - 1]).
Step 4: Fill the DP table bottom-up:
In each cell, starting with the second-to-last row and column, the current grid value is added after determining the largest value between the cell to the right and the cell below (dp[i][j] = grid[i][j] + Math.max(dp[i + 1][j], dp[i][j + 1])).
Step 5: Return dp[0][0].
Step 6: The outcome represents the maximum coins collected by taking the best route through the provided grid.
Let’s implement the above steps.
FileName: MaximumCoins1.java
public class MaximumCoins1 {
public static int maxCoinsDP(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int[][] dp = new int[rows][cols];
// Initialize the bottom-right cell
dp[rows - 1][cols - 1] = grid[rows - 1][cols - 1];
// Initialize the last row
for (int i = cols - 2; i >= 0; i--) {
dp[rows - 1][i] = grid[rows - 1][i] + dp[rows - 1][i + 1];
}
// Initialize the last column
for (int i = rows - 2; i >= 0; i--) {
dp[i][cols - 1] = grid[i][cols - 1] + dp[i + 1][cols - 1];
}
// Fill the DP table bottom-up
for (int i = rows - 2; i >= 0; i--) {
for (int j = cols - 2; j >= 0; j--) {
dp[i][j] = grid[i][j] + Math.max(dp[i + 1][j], dp[i][j + 1]);
}
}
// The result is stored in the top-left cell
return dp[0][0];
}
public static void main(String[] args) {
int[][] grid = {
{1, 3, 1},
{1, 5, 1},
{4, 2, 1}
};
System.out.println("Maximum number of coins collected: " + maxCoinsDP(grid));
}
}
Output:
Maximum number of coins collected: 12
Complexity Analysis: The solution provided by the dynamic programming approach is more effective and has an O(m * n) time complexity. By filling a dynamic programming table iteratively and eliminating pointless operations, it accomplishes this efficiency. Because this is the amount of space needed to store the dynamic programming table, the space complexity is also O(m * n).