Java
Understanding the Problem StatementThis problem involves a grid of integers (coins), where each cell contains a value representing coins you can collect or a pe


### Understanding the Problem Statement

This problem involves a grid of integers (`coins`), where each cell contains a value representing coins you can collect or a penalty (negative value). Starting from the top-left corner, the goal is to reach the bottom-right corner while maximizing the coins collected. You may move either **down** or **right**. Additionally, you are allowed to "ignore" negative penalties up to **two times** (`k=2`) during your journey.

---

### Code Breakdown and Explanation

The provided code solves the problem using **dynamic programming (DP)** and recursion. Let’s break down the solution step by step:

---

#### 1. **Initial Setup**

The class `Solution` includes:
- A 3D array `dp` to store intermediate results and avoid redundant calculations (memoization).
- Variables `m` and `n` to store the dimensions of the grid.

```java
Integer [][][] dp;
int m, n;
```

---

#### 2. **Core Functionality**

The key methods are:

1. **`maximumAmount(int[][] coins)`**:
   - Initializes `m`, `n`, and the `dp` array.
   - Calls the recursive helper function `solve` starting from the top-left cell `(0, 0)` with `k=2` remaining skips.

2. **`solve(int i, int j, int k, int[][] coins)`**:
   - A recursive function that explores all possible paths to maximize the coin collection.
   - Accounts for grid boundaries and skips penalties intelligently.

---

#### 3. **Recursive Logic**

**Base Case:**
- If the current position is out of bounds, return a large negative value (`Integer.MIN_VALUE`), as it is not a valid path.
- If we are at the bottom-right corner (`i == m - 1 && j == n - 1`):
  - If the value is positive or zero, return it.
  - If it’s negative, reduce it to 0 only if `k > 0` (i.e., a skip is available).

```java
if (i == m - 1 && j == n - 1) {
    int c = coins[i][j];
    if (c >= 0) dp[i][j][k] = c;
    else dp[i][j][k] = (k > 0) ? Math.max(c, 0) : c;
    return dp[i][j][k];
}
```

---

#### 4. **Recursive Transitions**

For each cell `(i, j)`:
1. Compute the maximum coins collected by moving **down** and **right**:
   ```java
   int down = solve(i + 1, j, k, coins); 
   int right = solve(i, j + 1, k, coins); 
   int best = Math.max(right, down);
   ```

2. Handle two cases for the current cell value `c = coins[i][j]`:
   - If `c >= 0`, add it to the `best` value.
   - If `c < 0`, decide between:
     - Paying the penalty: `c + best`.
     - Skipping the penalty (if `k > 0`), exploring the remaining paths with `k - 1` skips:
       ```java
       int skipDown = solve(i + 1, j, k - 1, coins); 
       int skipRight = solve(i, j + 1, k - 1, coins); 
       not = Math.max(skipDown, skipRight);
       dp[i][j][k] = Math.max(pay, not);
       ```

---

#### 5. **Memoization**

To avoid redundant calculations, the results for each state `(i, j, k)` are stored in the `dp` array. Before computing a result, the function checks if the value is already cached.

```java
if (dp[i][j][k] != null) {
    return dp[i][j][k];
}
```

---

### Example Walkthrough

For the input grid:

```
coins = [[ 0,  1, -1],
         [ 1, -2,  3],
         [ 2, -3,  4]]
```

1. Starting at `(0, 0)` with `k = 2`:
   - Possible moves: `(1, 0)` or `(0, 1)`.

2. At `(1, 0)`, compute:
   - Maximum coins collected by going down or right.
   - Handle the penalty `-2` at `(1, 1)` using one of the skips (`k - 1`).

3. Continue recursively until reaching the bottom-right corner `(2, 2)`.

---

### Output for Example Input

The optimal path is:  
`(0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2)`, with `k=1` skip used at `(1, 1)`.

The maximum coins collected = **9**.

---

### Key Points

- **Dynamic Programming** ensures efficiency by storing previously computed results.
- **Penalty Skipping** (`k > 0`) is critical to finding the optimal path.
- The solution explores all valid paths and handles negative penalties intelligently.

This approach ensures the problem is solved within acceptable time limits for large grids.
# Code
```java []
class Solution {
    Integer [][][] dp;
     int m,n;
    public int maximumAmount(int[][] coins) {
        m=coins.length;
        n=coins[0].length;
        dp = new Integer[m][n][3];
        return solve(0,0,2,coins);
    }

    private int solve(int i,int j,int k,int[][] coins){
        if(i<0 || j<0 || j>=n ||i>=m) return Integer.MIN_VALUE;
        if (dp[i][j][k] != null) {
            return dp[i][j][k];
        }
        if (i == m- 1 && j == n - 1){
            int c= coins[i][j];
            if(c>=0) dp[i][j][k]=c;
            else{
                if(k>0) dp[i][j][k] =Math.max(c,0);
                else dp[i][j][k]=c;
            }
            return dp[i][j][k];
        }
        int c=coins[i][j];
        int down = solve(i + 1, j, k,coins); 
        int right = solve(i, j + 1, k, coins); 
        int best=Math.max(right,down);
        if(c>=0){
            dp[i][j][k]=c+best;
        }else{
            int pay= c+best;
            int not = Integer.MIN_VALUE;
        if (k>0) {
            int skipDown = solve(i + 1, j, k - 1, coins); 
            int skipRight = solve(i, j + 1, k - 1, coins); 
            not = Math.max(skipDown, skipRight);
        }

        dp[i][j][k]= Math.max(pay,not);
        }
        return dp[i][j][k];
    }
}
```
['Java']