How to traverse a grid using two different paths to maximize the sum of the path

Problem

You are given an n x n integer grid (can contain negatives). Two paths must be chosen simultaneously under coupled movement rules:

• Path 1 starts at top-left (0,0) and must reach bottom-right (n-1,n-1) moving only Right (R) or Down (D).
• Path 2 starts at top-right (0,n-1) and must reach bottom-left (n-1,0) moving only Left (L) or Down (D).
• The moves are coupled step-by-step: at each time step you choose exactly one of two composite moves:
  1. (D for Path1, L for Path2)
  2. (R for Path1, D for Path2)

Thus every step advances both paths by one move. After exactly 2(n-1) coupled steps:

• Path 1 will have taken (n-1) downs and (n-1) rights → reaches (n-1,n-1).
• Path 2 will have taken (n-1) downs and (n-1) lefts → reaches (n-1,0).

Scoring: Each time a path occupies a cell, you add that cell's value to the total. If both paths occupy the same cell at the same step, its value is counted twice (one per path). (They may also traverse the same cell at different steps, again being counted once per visit.)

Goal: Maximize the total sum collected by both paths.

Return the maximum achievable sum.

Clarifications

• Grid is square (n x n). (Can be generalized to rectangular with straightforward indexing tweaks.)
• Negative values are allowed: skipping a negative cell may be impossible due to monotonic constraints, so DP must handle negatives (initialize with -inf).
• Overlap is allowed and not penalized; each visit contributes its cell value.

Examples

Example 1

Input: 
grid = [
        [ 6,  0,  3, -1],
        [ 7,  4,  2,  4],
        [-3,  3, -2,  8],
        [13, 10, -1, -4],
]
Output: 56

Explanation: For e.g. Path1 is colored in orange, path 2 in green, and overlapping cells in blue.

Collected sum = 56 (Path1 = 22, Path2 = 34, overlap cells contribute both values).

Example 2

Input:
n = 1, grid = [[5]]
Output: 10
Explanation: Both paths start and end on the single cell; its value counted twice.

Solution

We present two methods:

1. Exponential backtracking (pedagogical, impractical beyond small n).
2. Dynamic Programming with a 2D state exploiting coupling → O(n^2) time.

Method 1 - Backtracking Enumeration (Brute Force)

Intuition

Each of the 2(n-1) coupled steps chooses one of two composite moves: A = (D,L) or B = (R,D). Thus there are 2^{2(n-1)} sequences in the worst case. For each sequence we simulate both paths and accumulate the sum. This grows doubly-exponentially in n (effectively exponential in n).

Approach

1. Depth-first generate all binary strings of length 2(n-1) representing choices A or B.
2. Maintain positions (r1,c1) and (r2,c2); update per composite move.
3. Accumulate cell values (add both at each step).
4. Track best total.

Code

Python

def max_sum_two_paths_bruteforce(grid):
    n = len(grid)
    target_steps = 2 * (n - 1)
    best = float('-inf')

    def dfs(step, r1, c1, r2, c2, acc):
        nonlocal best
        if step == target_steps:
            best = max(best, acc)
            return
        # Move A: (D,L)
        if r1 + 1 < n and c2 - 1 >= 0:
            dfs(step + 1, r1 + 1, c1, r2, c2 - 1, acc + grid[r1 + 1][c1] + grid[r2][c2 - 1])
        # Move B: (R,D)
        if c1 + 1 < n and r2 + 1 < n:
            dfs(step + 1, r1, c1 + 1, r2 + 1, c2, acc + grid[r1][c1 + 1] + grid[r2 + 1][c2])

    # initial contribution includes both starting cells
    dfs(0, 0, 0, 0, n - 1, grid[0][0] + (grid[0][n - 1] if n > 1 else grid[0][0]))
    return best

Complexity

• ⏰ Time complexity: O(2^{2(n-1)}) – every step branches into 2; depth 2(n-1). Completely infeasible for moderate n.
• 🧺 Space complexity: O(n) – recursion depth proportional to steps; ignoring output since we keep only best.

Method 2 - Dynamic Programming (State Compression to 2D)

Intuition

At each coupled step exactly one of the two paths moves Down; the other moves horizontally (Right for Path1 or Left for Path2). Let:

• r1 = number of Down moves taken by Path1 so far.
• r2 = number of Down moves taken by Path2 so far.

Total steps taken so far = t = r1 + r2 (because each step increments exactly one of r1 or r2).

From this we derive current coordinates:

• Path1: (r1, c1) with c1 = number_of_R_moves = t - r1 = r2 → (r1, r2).
• Path2: (r2, c2) with number_of_L_moves = t - r2 = r1 so c2 = (n - 1) - r1 → (r2, n - 1 - r1).

Thus a state is uniquely identified by the pair (r1, r2); positions can be computed, eliminating the step dimension. Transitions:

• Previous state could be (r1-1, r2) if we just executed composite (D,L).
• Or (r1, r2-1) if we just executed composite (R,D).

Score addition for state (r1, r2):

value = grid[r1][r2] + grid[r2][n-1 - r1]

If paths share the same cell in this same step (only possible when r1 == r2 and r2 == n-1 - r1 ⇒ center of an odd-sized grid) we still count twice per the problem’s rule; no adjustment needed.

Recurrence

Let dp[r1][r2] = maximum sum after r1 downs by Path1 and r2 downs by Path2.

Base:

dp[0][0] = grid[0][0] + grid[0][n-1]

Transition (for r1, r2 ≥ 0):

dp[r1][r2] = max(
    dp[r1-1][r2] if r1 > 0,
    dp[r1][r2-1] if r2 > 0
) + grid[r1][r2] + grid[r2][n-1 - r1]

Answer: dp[n-1][n-1] (Path1 at (n-1,n-1), Path2 at (n-1,0)).

Approach

1. Initialize dp with -inf.
2. Fill row by row (or any order ensuring dependencies (r1-1,r2) and (r1,r2-1) processed first).
3. Return dp[n-1][n-1].
4. Space optimize to O(n) by rolling over r1 or r2 dimension.

Pseudocode

dp = matrix n x n filled with -inf
dp[0][0] = grid[0][0] + grid[0][n-1]
for r1 in 0..n-1:
  for r2 in 0..n-1:
    if r1 == 0 and r2 == 0: continue
    best_prev = max(dp[r1-1][r2] if r1>0, dp[r1][r2-1] if r2>0)
    dp[r1][r2] = best_prev + grid[r1][r2] + grid[r2][n-1-r1]
return dp[n-1][n-1]

Code

Java

public class Solution {
    public int maximizeTwoCoupledPaths(int[][] grid) {
        int n = grid.length;
        int NEG_INF = Integer.MIN_VALUE / 4; // avoid overflow
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) dp[i][j] = NEG_INF;
        }
        dp[0][0] = grid[0][0] + (n > 1 ? grid[0][n-1] : grid[0][0]);
        for (int r1 = 0; r1 < n; r1++) {
            for (int r2 = 0; r2 < n; r2++) {
                if (r1 == 0 && r2 == 0) continue;
                int bestPrev = NEG_INF;
                if (r1 > 0) bestPrev = Math.max(bestPrev, dp[r1-1][r2]);
                if (r2 > 0) bestPrev = Math.max(bestPrev, dp[r1][r2-1]);
                if (bestPrev == NEG_INF) continue;
                int val = grid[r1][r2] + grid[r2][n-1 - r1];
                dp[r1][r2] = bestPrev + val;
            }
        }
        return dp[n-1][n-1];
    }
}

Python

from typing import List

class Solution:
    def maximizeTwoCoupledPaths(self, grid: List[List[int]]) -> int:
        n = len(grid)
        NEG_INF = float('-inf')
        dp = [[NEG_INF]*n for _ in range(n)]
        dp[0][0] = grid[0][0] + (grid[0][n-1] if n > 1 else grid[0][0])
        for r1 in range(n):
            for r2 in range(n):
                if r1 == 0 and r2 == 0:
                    continue
                best_prev = NEG_INF
                if r1 > 0:
                    best_prev = max(best_prev, dp[r1-1][r2])
                if r2 > 0:
                    best_prev = max(best_prev, dp[r1][r2-1])
                if best_prev == NEG_INF:
                    continue
                val = grid[r1][r2] + grid[r2][n-1 - r1]
                dp[r1][r2] = best_prev + val
        return dp[n-1][n-1]

Complexity

• ⏰ Time complexity: O(n * n) – n^2 states; each in O(1) from two predecessors.
• 🧺 Space complexity: O(n * n) – DP table; reducible to O(n) with rolling array.

Trade-offs

Method	Time	Space	Notes
1 Brute Force	O(2^{2(n-1)})	O(n)	Only for intuition / tiny n.
2 DP 2D	O(n^2)	O(n^2) (O(n) opt)	Practical and optimal under constraints.

Edge Cases

1. n = 1 – both paths same single cell; counted twice.
2. All negatives – DP still valid; ensures maximum (least negative) path pair.
3. Large positive on one side – DP naturally steers composite moves to harvest both extremes.
4. Center overlap (odd n) – counted twice per rules (no adjustment needed).