🧩 Python DSA Patterns — DP on Grids 🧩🐍

2D Grid Dynamic Programming problems appear whenever movement is restricted inside a matrix — such as moving right/down, navigating paths with obstacles, or computing optimal costs.

The core idea is simple:

👉 Store the best possible answer at each cell, derived from its neighboring cells.

Once you understand how to define the DP state per cell, grid problems become systematic instead of confusing.

📝 Unique Paths (Basic Grid DP)

We count the number of ways to reach each cell using results from the top and left neighbors.

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    print("Unique Paths:", dp[-1][-1])

💡 Why it works: Each cell can only be reached from the cell above or the cell to the left.

📝 Minimum Path Sum in a Grid

Instead of counting paths, we now minimize the total cost to reach each cell.

def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]

    for i in range(1, rows):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, cols):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    print("Minimum Path Sum:", dp[-1][-1])

💡 Key change: The transition uses min() instead of addition.

📝 Maximal Square in a Binary Matrix

This problem finds the largest square of 1s inside a matrix.

def maximal_square(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dp = [[0]*(cols+1) for _ in range(rows+1)]
    max_side = 0

    for i in range(1, rows+1):
        for j in range(1, cols+1):
            if matrix[i-1][j-1] == '1':
                dp[i][j] = 1 + min(
                    dp[i-1][j],
                    dp[i][j-1],
                    dp[i-1][j-1]
                )
                max_side = max(max_side, dp[i][j])

    print("Maximal Square Area:", max_side * max_side)

💡 Insight: A square can grow only if top, left, and diagonal cells support it.

📝 Unique Paths with Obstacles

Some cells are blocked — paths passing through them are invalid.

def unique_paths_with_obstacles(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]

    if grid[0][0] == 1:
        print("Unique Paths with Obstacles: 0")
        return

    dp[0][0] = 1

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                dp[i][j] = 0
            else:
                if i > 0:
                    dp[i][j] += dp[i-1][j]
                if j > 0:
                    dp[i][j] += dp[i][j-1]

    print("Unique Paths with Obstacles:", dp[-1][-1])

🧠 Where Grid DP Is Used

• 🗺️ Pathfinding problems
• 🧩 Image & matrix processing
• 📦 Robotics navigation
• 🎮 Game boards
• 📊 Grid-based optimizations

✅ Takeaway

• Grid DP stores answers per cell
• Transitions usually come from:
  • 🔼 Top
  • ◀️ Left
  • ↖️ Diagonal
• Always define:
  • What dp[i][j] means
  • Base cases
  • Valid transitions

Once this pattern clicks, most grid DP problems feel repetitive — in a good way.

🏋️ Practice Problems

1. Unique Paths
2. Unique Paths with Obstacles
3. Minimum Path Sum
4. Maximal Square
5. Dungeon Game

📂 Full Script

The blog covers the essentials — find the complete notebook with all snippets & extras on GitHub Repo 👉 Python DSA Patterns