Dynamic Programming: Finding the Safest Climbing Path

Problem Description

Imagine a rock climber facing a climbing wall made up of square blocks. Each block represents a potential handhold with an associated danger rating. The climber’s goal is to find the safest path from the bottom to the top of the wall, where safety is measured by minimizing the sum of danger ratings along the path.

Problem Constraints

1. The wall is represented as an m × n grid of blocks
2. Each block has a positive danger rating
3. From any block (except at the edges), the climber can reach:
   • The block directly above
   • The block towards upper-right
   • The block towards upper-left
4. The goal is to minimize the total danger rating of the path

Example

For a 4 × 5 climbing wall, the danger ratings might be:

2  8  9  5  8
4  4  6  2  3
5  7  5  6  1
3  2  5  4  8

Understanding the Solution

Dynamic Programming Approach

This problem is well-suited for dynamic programming because:

• It has optimal substructure (best path to any position includes best paths to positions below it)
• It has overlapping subproblems (many paths share common sub-paths)

Let’s break down the solution step by step.

1. State Definition

Let dp[i][j] represent the minimum total danger rating to reach the top row from position (i,j).

2. Recurrence Relation

For each position (i,j), we can reach it from three possible lower positions:

3. Base Cases

• When i = 1 (top row): dp[1][j] = grid[1][j]

Solution Implementation

def find_safest_climbing_path(grid):
    m, n = len(grid), len(grid[0])
    
    # Create DP table initialized with infinity
    dp = [[float('inf')] * (n + 2) for _ in range(m + 1)]  # Extra columns for padding
    
    # Initialize the top row (base case)
    for j in range(1, n + 1):
        dp[1][j] = grid[0][j-1]  # 0-based indexing for input grid
    
    # Fill DP table bottom-up
    for i in range(2, m + 1):
        for j in range(1, n + 1):
            # Get value from input grid (adjusting for 0-based indexing)
            current_danger = grid[i-1][j-1]
            
            # Find minimum from three possible moves
            dp[i][j] = current_danger + min(
                dp[i-1][j-1],  # upper-left
                dp[i-1][j],    # directly above
                dp[i-1][j+1]   # upper-right
            )
    
    # Find minimum cost path starting from bottom row
    min_danger = float('inf')
    best_start = 0
    
    for j in range(1, n + 1):
        if dp[m][j] < min_danger:
            min_danger = dp[m][j]
            best_start = j
            
    # Reconstruct the path
    path = []
    current_j = best_start
    
    for i in range(m, 0, -1):
        path.append((i-1, current_j-1))  # Convert to 0-based indices
        if i > 1:  # Not at top row yet
            # Find which move was taken to reach current position
            options = [
                (dp[i-1][current_j-1], current_j-1),  # upper-left
                (dp[i-1][current_j], current_j),      # directly above
                (dp[i-1][current_j+1], current_j+1)   # upper-right
            ]
            _, current_j = min(options)
    
    return min_danger, path[::-1]  # Reverse path to go bottom-to-top

# Example usage
def main():
    # Example climbing wall
    grid = [
        [2, 8, 9, 5, 8],
        [4, 4, 6, 2, 3],
        [5, 7, 5, 6, 1],
        [3, 2, 5, 4, 8]
    ]
    
    danger_rating, path = find_safest_climbing_path(grid)
    print(f"Minimum danger rating: {danger_rating}")
    print("Path (row, column):")
    for pos in path:
        print(f"  {pos}")
        
    # Visualize the path
    def visualize_path(grid, path):
        path_set = set(path)
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if (i, j) in path_set:
                    print(f"[{grid[i][j]}]", end=" ")
                else:
                    print(f" {grid[i][j]} ", end=" ")
            print()
    
    print("\nVisualized path ([] marks the chosen route):")
    visualize_path(grid, path)

if __name__ == "__main__":
    main()

Complexity Analysis

Time Complexity

• $O(m \times n)$ where:
  • m is the number of rows
  • n is the number of columns
• We visit each position exactly once
• At each position, we consider three possible moves

Space Complexity

• $O(m \times n)$ for the dp table
• Additional $O(m)$ for storing the path