Ninja and His Friends

Implement ninjaAndFriends

Two friends start together on the top row of a grid — one at the first column, the other at the last column — and both move down one row at a time until they reach the bottom. At every row, each friend independently moves to the column directly below, or one column to either side. Find the maximum total value the two friends can collect together, where a cell they both land on at the same time only counts once. Every pair of positions' best outcome downward depends only on the (up to nine) pairs of positions reachable one row below, so working from the bottom row upward — where a pair's best outcome is simply the value(s) at that row — lets each row above be resolved using a table the sweep already computed. By the time the sweep reaches the top row, the entry for the friends' actual starting columns holds the maximum total collectible across the whole grid.

Example 1:

Input: grid = [[3,5,2],[6,2,7],[4,3,6]]

Output: 28

Example 2:

Input: grid = [[1,2],[3,4]]

Output: 10

Example 3:

Input: grid = [[5,1,5]]

Output: 10

+ 7 hidden test cases run on Submit.

Constraints:

  • 1 ≤ grid.length (rows) ≤ 15
  • 1 ≤ grid[0].length (columns) ≤ 15
  • 0 ≤ grid[i][j] ≤ 100

grid =

[[3,5,2], [6,2,7], [4,3,6]]