Minimum Cost Path with Alternating Directions II - Solution & Explanation

Problem Overview: You are given a cost matrix and need the minimum cost to travel from the top-left cell to the bottom-right cell. The constraint: consecutive moves must alternate direction types (horizontal vs vertical). Every move adds the cost of the destination cell, so the challenge is tracking both position and the last direction used.

Approach 1: Brute Force DFS with Direction Tracking (Exponential Time, O(2^(m*n)) time, O(m*n) recursion space)

Start a depth‑first search from (0,0). At each cell, try valid moves that alternate direction from the previous step. For example, if the last move was horizontal, the next must be vertical. Track visited states and accumulate path cost until reaching the bottom-right cell. This approach explores many repeated states because the same cell can be reached with different previous directions, making the runtime exponential. Useful mainly for understanding the constraint and validating small inputs.

Approach 2: Dynamic Programming with Direction State (O(m*n) time, O(m*n) space)

The key observation: the optimal cost for a cell depends on both its coordinates and the direction used to reach it. Maintain two DP states per cell: dp[i][j][0] for arriving via a horizontal move and dp[i][j][1] for arriving via a vertical move. When transitioning, enforce alternation: horizontal states transition from vertical states and vice versa. Iterate through the grid and update costs using the minimum previous valid state. Each state is processed once, giving O(m*n) time with constant work per transition.

Using a direction-aware DP avoids recomputation and models the constraint directly in the state. The idea is similar to grid problems where movement history matters, commonly solved with Dynamic Programming on a Matrix. The grid itself is treated like a graph where each cell has two directional states, a pattern also seen in constrained path problems over Array-based grids.

Recommended for interviews: The dynamic programming approach with a direction state is what interviewers expect. A brute force DFS demonstrates understanding of the alternating constraint, but the DP solution shows you can convert repeated subproblems into a state transition and reduce the complexity to linear in the number of cells.