Algorithm

Steps to Convert Recursive Solution to Tabulation

Tabulation uses the same 3D table as memoization. For example, one cell in the table shows the maximum chocolates collected when Alice and Bob are at specific positions in the same row.

Base Setup

Since the last row is the stopping point in recursion, fill the last row of the table first: If Alice and Bob are in the same cell, count chocolates once. If in different cells, add chocolates from both cells.

Filling the Table

Go row by row from the second last row up to the first row.
For each pair of positions of Alice and Bob, check all 9 possible move combinations (down, down-left, down-right for each).
For each option, look at the values already stored in the next row and add chocolates collected in the current move.
Keep the highest value among all 9 options as the best result for that cell.

Final Answer

After filling the table, the top row’s starting positions give the maximum chocolates Alice and Bob can collect together.

Code

#incl