Lightoj 1004 Solution in English

Lightoj 1004 Solution in English

Problem Link: Lightoj 1004

Click Here to see the discussion in Bangla

First, let me say this is a simple DP (Dynamic Programming) problem.

If you know the Rock Climbing problem, this one will feel very similar. If not, it’s better to learn that first (there are Bengali blogs about it). Anyway, let’s discuss the problem.

We are given a diamond-shaped 2D array.

Each cell of the array contains some bananas 🍌.

A monkey starts from the top of the diamond and can only move downward to adjacent cells.

Whenever the monkey visits a cell, it eats all the bananas in that cell.

So, our task is to find the maximum number of bananas the monkey can eat by choosing the best possible path. 

                                                             

Step 1: Understanding the movement

• The monkey can only move to adjacent cells below the current cell.

• For example, if the monkey is at [1,1] (with 7 bananas), it can go to [2,1] or [2,2].

• Now, which one should it choose? The answer depends on which path eventually gives more bananas.

• So, we must check all possible paths to know the maximum.

This can naturally be solved using recursion:

• At each cell, check all possible next moves.

• Take the path that yields the maximum bananas.

Step 2: Why recursion is not enough

Although recursion works, it will cause a TLE (Time Limit Exceeded).
Why?
Because the monkey can revisit the same cell multiple times from different paths, and each time, recursion will recompute the result for that subproblem.

If you print row/column indices during recursion, you’ll see that many cells are visited multiple times.

Step 3: Adding DP (Memoization)

To avoid recomputing, we use DP (Dynamic Programming):

• We store the result (maximum bananas from this cell onward) in a DP array.

• If we reach the same cell again, we don’t recurse further. Instead, we directly return the stored result.

• This way, each cell is computed only once, making the solution efficient.

Step 4: Special case for diamond shape

Since the array is diamond-shaped, there are two phases:

1. Expanding rows (from top to middle).

2. Contracting rows (from middle to bottom).

That’s why the recursive function uses two conditions for handling movement in different halves of the diamond.