Inspired by and learned from TakeUForward.

After solving several Grid DP problems, I realized that most of them follow a common pattern. Instead of memorizing solutions, I now try to classify the problem first.

Step 1: Identify the Starting and Ending Points

The first thing I ask is:

• Is there a single starting point or multiple starting points?

• Is there a single ending point or multiple ending points?

This usually tells me the direction in which my recursion should flow.

Common Patterns

Pattern	Example
Single Start → Single End	Unique Paths
Single Start → Variable End	Minimum Falling Path Sum
Variable Start → Variable End	Minimum Path Cost in a Grid
Multiple Starts → Variable End	Cherry Pickup II / Ninja's Training II
Variable Start → Single End	Less common but possible

Once I identify the pattern, defining the recursive state becomes much easier.

---

Step 2: Build the Recursive Function

I always think of recursion as:

"From my current position, what is the best answer I can get?"

General template:

int solve(state) {
    // base condition

    // consume current value

    // explore all possible moves

    // return best answer
}

The flow is:

1. Consume the current cell/value.

2. Find all possible next moves.

3. Ask recursion for the answer from those moves.

4. Combine the results.

---

Step 3: Understand the Objective

Most Grid DP problems fall into one of these categories:

Count Problems

Examples:

• Unique Paths

• Unique Paths II

return left + right;

Every valid path contributes to the final answer.

---

Maximum Problems

Examples:

• Ninja's Training - On TakeUForward

• Cherry Pickup II - On TakeUForward

return currentValue + max(all options);

Choose the path that gives the highest score.

---

Minimum Problems

Examples:

• Minimum Falling Path Sum

• Minimum Path Sum

return currentValue + min(all options);

Choose the path with the lowest cost.

---

Step 4: Generate Options

Fixed Number of Options

Example:

Move only:

• Up

• Left

solve(i-1, j)
solve(i, j-1)

Direct recursive calls are sufficient.

---

Variable Number of Options

Example:

Move to:

• Left Diagonal

• Up

• Right Diagonal

or

Robot A and Robot B moving independently.

Use loops.

for(int move=-1; move<=1; move++){
    ...
}

When the number of choices grows, loops keep the code cleaner and scalable.

---

Step 5: Verify Recursion on a Small Example

Before memoization, I manually test:

• 1x1 grid

• 2x2 grid

• Small custom examples

Questions I ask:

• Is the base condition correct?

• Am I consuming the current cell exactly once?

• Are all valid options explored?

• Are invalid states handled properly?

---

Step 6: Memoization

At this stage I ask:

"What variables uniquely identify the state?"

Examples:

Single Position

dp[i][j]

Example:

• Unique Paths

• Minimum Path Sum

---

Position + Previous Choice

dp[day][lastTask]

Example:

• Ninja's Training

---

Two Independent Positions

dp[row][robot1][robot2]

Example:

• Cherry Pickup II

The dimensions of the DP array directly come from the parameters of the recursive function.

---

Step 7: Convert Memoization to Tabulation

Once memoization is working, tabulation becomes much easier.

Questions:

What are the base conditions?

Those become the first values filled in the DP table.

Which states depend on which states?

That determines the iteration order.

If recursion goes:

solve(i)
-> solve(i+1)

Tabulation usually runs:

for(i=n-2; i>=0; i--)

because future states must already be computed.

---

My Mental Model

Memoization:

"Ask for answers when needed."

I call this:

Lazy Learning.

---

Tabulation:

"Build all answers beforehand."

I call this:

Eager Learning.

---

Common Grid DP Checklist

Before coding:

• What is my state?

• What are the base conditions?

• What value am I returning?

• Count / Maximum / Minimum?

• What are my valid moves?

• How do I handle invalid moves?

• Can I memoize using only the changing parameters?

If I can answer these questions clearly, the solution is usually close.

---

Problems That Helped Me Learn

Single Start → Single End

1. Ninja's Training

2. Grid Unique Paths

3. Unique Paths II

---

Single Start → Variable End

1. Minimum Falling Path Sum

---

Variable Start → Variable End

1. Minimum Path Cost in a Grid

---

Multiple Start → Variable End

1. Cherry Pickup II (Ninja's Training II)

---

Biggest Lesson

The hardest part of Grid DP is not memoization or tabulation.

The hardest part is defining the state correctly.

Once the state is correct:

Recursion → Memoization → Tabulation becomes almost mechanical.