Minimum Cost Path With At Most K Turns solution and explanation

Problem Overview: You are given an m x n grid where each cell has a cost, and you need to travel from (0,0) to (m-1,n-1) using up, down, left, or right moves. The path can contain at most K turns (a turn is a direction change). Find the minimum total cost of such a path, including the cost of the starting and ending cells.

Approach 1: Brute Force DFS with Backtracking (Exponential Time)

Enumerate every possible path using recursive DFS. Carry the current cell, the current direction, and the number of turns used so far. At each step try all four moves. When moving in a direction different from the current direction, increment the turn count. Prune any branch where the turn count exceeds K or you step off the grid. This explores all paths, leading to O(4^(m*n)) time and O(m*n) recursion stack. It is only practical for very small grids, but it is useful to verify the correctness of an optimal algorithm on test cases.

Approach 2: Dijkstra's Algorithm on a State Graph (Optimal, O(m*n*K*4 log(m*n*K*4)))

The key insight is that the total cost to reach a specific cell is not enough — the direction you arrived from and how many turns you have already used affect future moves. So model the problem as a shortest path on a state graph where each node is (row, col, direction, turnsUsed). There are 4 possible directions and 0..K turn counts, giving m*n*4*(K+1) states. An edge from a state to a neighboring cell has a cost equal to the neighbor's cell value; if moving in the same direction the turn count stays the same, otherwise it increments by 1. Skip transitions where the new turn count exceeds K.

Use a min-heap (priority queue) to always expand the lowest-cost state, similar to standard Dijkstra. Initialize the start cell with all four directions and turnsUsed = 0 (since there is no previous direction, you can start in any direction for free). When you pop a state that reaches the destination, the heap guarantee means you have found the minimum cost. Alternatively, you can track the minimum cost to each state in a 4D distance array and when the destination is popped for the first time, return the cost.

Because cell costs are non-negative, Dijkstra is correct. The time complexity is O(m*n*K*4 log(m*n*K*4)) because each state is pushed and popped at most once. The space complexity is O(m*n*K*4) for the distance array plus the heap overhead in the worst case.

Approach 3: Why Standard DP Does Not Work Here

You might think a flat m x n DP table would solve this, but the turn constraint and ability to move in all four directions create cycles. A classic DP requires a topological order, which does not exist in an undirected grid with positive costs. Dijkstra avoids this by relaxing states multiple times and using a global priority criterion.

Recommended for interviews: Explain the brute-force DFS first to demonstrate your understanding of the state space. Then present the Dijkstra state-graph solution. The moment you say “the state must include the direction and the number of turns used” is the moment interviewers know you have solved similar graph problems. Mention the 4D distance array and the min-heap explicitly. The brute force shows fundamentals; the Dijkstra solution shows mastery of shortest-path algorithms under constraints. For more practice, explore related problems in the graph topic and the shortest path collection. You can also review heap-based algorithms for other pathfinding problems.