Climbing Stairs and Variations: Building Intuition with Step-Counting Problems

def climbing_stairs_analysis():
    """
    Step-by-step analysis of the climbing stairs problem
    """
    
    # Step 1: Understand the problem
    """
    - Input: n (number of steps)
    - Output: number of distinct ways to reach step n
    - Rules: can climb 1 or 2 steps at a time
    - Type: Pure counting problem
    """
    
    # Step 2: State definition
    """
    State: dp[i] = number of ways to reach step i
    """
    
    # Step 3: Transition relation
    """
    To reach step i, you must come from:
    - Step i-1 (take 1 step)
    - Step i-2 (take 2 steps)
    
    Therefore: dp[i] = dp[i-1] + dp[i-2]
    """
    
    # Step 4: Base cases
    """
    dp[0] = 1 (one way to stay at ground - do nothing)
    dp[1] = 1 (only one way to reach step 1)
    """
    
    # Step 5: Pattern recognition
    """
    This is the Fibonacci sequence!
    F(n+1) = ways to climb n stairs
    """

def climb_stairs(n):
    """
    Optimized solution for climbing stairs
    Time: O(n), Space: O(1)
    """
    if n <= 1:
        return 1
    
    prev2 = 1  # ways to reach step 0
    prev1 = 1  # ways to reach step 1
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    
    return prev1

def climb_stairs_three_steps(n):
    """
    Can climb 1, 2, or 3 steps at a time
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    """
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    # Space-optimized approach
    a, b, c = 1, 1, 2  # dp[0], dp[1], dp[2]
    
    for i in range(3, n + 1):
        next_val = a + b + c
        a, b, c = b, c, next_val
    
    return c

def climb_stairs_with_trace_three(n):
    """
    Show the calculation process for three-step climbing
    """
    print(f"Calculating ways to climb {n} stairs (1, 2, or 3 steps):")
    
    if n <= 2:
        return [1, 1, 2][n]
    
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    dp[2] = 2
    
    print(f"dp[0] = 1, dp[1] = 1, dp[2] = 2")
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
        print(f"dp[{i}] = dp[{i-1}] + dp[{i-2}] + dp[{i-3}] = {dp[i-1]} + {dp[i-2]} + {dp[i-3]} = {dp[i]}")
    
    return dp[n]

def climb_stairs_custom_steps(n, allowed_steps):
    """
    General solution for any set of allowed step sizes
    
    Args:
        n: number of stairs
        allowed_steps: list of allowed step sizes (e.g., [1, 2, 3])
    
    Returns:
        number of ways to climb n stairs
    """
    if n == 0:
        return 1
    
    dp = [0] * (n + 1)
    dp[0] = 1
    
    for i in range(1, n + 1):
        for step in allowed_steps:
            if i >= step:
                dp[i] += dp[i - step]
    
    return dp[n]

def demonstrate_custom_patterns():
    """
    Demonstrate different step patterns
    """
    test_cases = [
        ([1, 2], "Standard (1 or 2 steps)"),
        ([1, 3, 5], "Odd steps only"),
        ([2, 4], "Even steps only"),
        ([1, 2, 3, 4, 5], "Up to 5 steps")
    ]
    
    n = 10
    for steps, description in test_cases:
        ways = climb_stairs_custom_steps(n, steps)
        print(f"{description}: {ways} ways to climb {n} stairs")

def min_cost_climbing_stairs(cost):
    """
    Find minimum cost to reach the top of stairs
    You can start from step 0 or step 1
    From each step, you can climb 1 or 2 steps
    
    Args:
        cost: list where cost[i] is the cost of stepping on step i
    
    Returns:
        minimum cost to reach beyond the last step
    """
    n = len(cost)
    if n <= 1:
        return 0
    
    # dp[i] = minimum cost to reach step i
    prev2 = cost[0]  # cost to reach step 0
    prev1 = cost[1]  # cost to reach step 1
    
    for i in range(2, n):
        current = cost[i] + min(prev1, prev2)
        prev2, prev1 = prev1, current
    
    # Can reach top from either of last two steps
    return min(prev1, prev2)

def min_cost_with_detailed_trace(cost):
    """
    Show the decision process for minimum cost climbing
    """
    print(f"Cost array: {cost}")
    n = len(cost)
    
    if n <= 1:
        return 0
    
    dp = [0] * n
    dp[0] = cost[0]
    dp[1] = cost[1]
    
    print(f"dp[0] = {dp[0]} (start at step 0)")
    print(f"dp[1] = {dp[1]} (start at step 1)")
    
    for i in range(2, n):
        from_prev1 = dp[i-1] + cost[i]
        from_prev2 = dp[i-2] + cost[i]
        dp[i] = min(from_prev1, from_prev2)
        
        choice = f"from step {i-1}" if from_prev1 < from_prev2 else f"from step {i-2}"
        print(f"dp[{i}] = {cost[i]} + min({dp[i-1]}, {dp[i-2]}) = {dp[i]} ({choice})")
    
    result = min(dp[n-1], dp[n-2])
    print(f"Final: min(dp[{n-1}], dp[{n-2}]) = {result}")
    return result

def unique_paths_2d(m, n):
    """
    Count unique paths in m x n grid from top-left to bottom-right
    Can only move right or down
    
    This extends 1D step counting to 2D
    """
    # Create DP table
    dp = [[0] * n for _ in range(m)]
    
    # Base cases: first row and first column
    for i in range(m):
        dp[i][0] = 1  # only one way to reach any cell in first column
    for j in range(n):
        dp[0][j] = 1  # only one way to reach any cell in first row
    
    # Fill the table
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]  # from above or from left
    
    return dp[m-1][n-1]

def unique_paths_optimized(m, n):
    """
    Space-optimized version using only one row
    Time: O(m*n), Space: O(n)
    """
    dp = [1] * n  # Initialize first row
    
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]  # dp[j] was dp[i-1][j], dp[j-1] is dp[i][j-1]
    
    return dp[n-1]

def unique_paths_with_obstacles(obstacle_grid):
    """
    Unique paths with obstacles in the grid
    obstacle_grid[i][j] = 1 means there's an obstacle
    """
    if not obstacle_grid or obstacle_grid[0][0] == 1:
        return 0
    
    m, n = len(obstacle_grid), len(obstacle_grid[0])
    dp = [[0] * n for _ in range(m)]
    
    # Base case: starting position
    dp[0][0] = 1
    
    # Fill first row
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] if obstacle_grid[0][j] == 0 else 0
    
    # Fill first column
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] if obstacle_grid[i][0] == 0 else 0
    
    # Fill the rest of the table
    for i in range(1, m):
        for j in range(1, n):
            if obstacle_grid[i][j] == 0:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            # else dp[i][j] remains 0 (obstacle)
    
    return dp[m-1][n-1]

def min_path_sum_2d(grid):
    """
    Find path from top-left to bottom-right with minimum sum
    Can only move right or down
    
    This changes from counting to optimization
    """
    if not grid:
        return 0
    
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    
    # Base case
    dp[0][0] = grid[0][0]
    
    # Fill first row
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    # Fill first column
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    
    # Fill the rest
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    
    return dp[m-1][n-1]

def min_path_sum_optimized(grid):
    """
    Space-optimized version modifying grid in-place
    """
    if not grid:
        return 0
    
    m, n = len(grid), len(grid[0])
    
    # Fill first row
    for j in range(1, n):
        grid[0][j] += grid[0][j-1]
    
    # Fill first column
    for i in range(1, m):
        grid[i][0] += grid[i-1][0]
    
    # Fill the rest
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])
    
    return grid[m-1][n-1]

def climb_stairs_forbidden_steps():
    """
    Problem: Climb stairs but certain steps are forbidden
    Can't step on steps marked as forbidden
    """
    
    def climb_with_forbidden(n, forbidden_steps):
        """
        Count ways to climb n stairs avoiding forbidden steps
        
        Args:
            n: total stairs
            forbidden_steps: set of step indices that can't be used
        """
        if n <= 0:
            return 1
        
        dp = [0] * (n + 1)
        dp[0] = 1  # one way to stay at start
        
        for i in range(1, n + 1):
            if i not in forbidden_steps:
                # Can reach step i from step i-1 (if we can step on i-1)
                if i >= 1:
                    dp[i] += dp[i-1]
                # Can reach step i from step i-2 (if we can step on i-2)
                if i >= 2:
                    dp[i] += dp[i-2]
        
        return dp[n]
    
    def climb_forbidden_with_trace(n, forbidden_steps):
        """Show the calculation with forbidden steps"""
        print(f"Climbing {n} stairs, forbidden steps: {forbidden_steps}")
        
        dp = [0] * (n + 1)
        dp[0] = 1
        print(f"dp[0] = 1 (base case)")
        
        for i in range(1, n + 1):
            if i in forbidden_steps:
                dp[i] = 0
                print(f"dp[{i}] = 0 (forbidden step)")
            else:
                ways = 0
                if i >= 1:
                    ways += dp[i-1]
                if i >= 2:
                    ways += dp[i-2]
                dp[i] = ways
                
                sources = []
                if i >= 1 and dp[i-1] > 0:
                    sources.append(f"dp[{i-1}]={dp[i-1]}")
                if i >= 2 and dp[i-2] > 0:
                    sources.append(f"dp[{i-2}]={dp[i-2]}")
                
                source_str = " + ".join(sources) if sources else "0"
                print(f"dp[{i}] = {source_str} = {dp[i]}")
        
        return dp[n]

# Test with forbidden steps
test_cases = [
    (5, {3}),      # Can't step on step 3
    (6, {2, 4}),   # Can't step on steps 2 and 4
    (7, {1, 3, 5}) # Can't step on multiple steps
]

for n, forbidden in test_cases:
    result = climb_forbidden_with_trace(n, forbidden)
    print(f"Ways to climb {n} stairs avoiding {forbidden}: {result}\n")

def circular_staircase_problem():
    """
    Problem: Count ways around a circular staircase
    You can go clockwise or counterclockwise, 1 or 2 steps at a time
    """
    
    def count_ways_circular(n, target_position):
        """
        Count ways to reach target_position on a circular staircase with n steps
        
        Args:
            n: total steps in circle (positions 0 to n-1)
            target_position: where we want to end up
        
        Returns:
            number of ways to reach target in exactly n moves
        """
        # This becomes a more complex DP problem
        # State: dp[moves][position] = ways to be at position after moves steps
        
        dp = [[0] * n for _ in range(n + 1)]
        dp[0][0] = 1  # start at position 0 with 0 moves
        
        for moves in range(1, n + 1):
            for pos in range(n):
                # From current position, where could we have come from?
                
                # Clockwise 1 step (came from pos-1)
                prev_pos = (pos - 1) % n
                dp[moves][pos] += dp[moves-1][prev_pos]
                
                # Clockwise 2 steps (came from pos-2)
                prev_pos = (pos - 2) % n
                dp[moves][pos] += dp[moves-1][prev_pos]
                
                # Counterclockwise 1 step (came from pos+1)
                prev_pos = (pos + 1) % n
                dp[moves][pos] += dp[moves-1][prev_pos]
                
                # Counterclockwise 2 steps (came from pos+2)
                prev_pos = (pos + 2) % n
                dp[moves][pos] += dp[moves-1][prev_pos]
        
        return dp[n][target_position]
    
    # Test circular staircase
    n = 6
    for target in range(n):
        ways = count_ways_circular(n, target)
        print(f"Ways to reach position {target} in {n} moves: {ways}")

def multi_dimensional_steps():
    """
    Problem: Count paths in 3D space or with multiple constraints
    """
    
    def count_paths_3d(x, y, z):
        """
        Count paths from (0,0,0) to (x,y,z)
        Can move +1 in any dimension
        """
        # 3D DP table
        dp = [[[0 for _ in range(z+1)] for _ in range(y+1)] for _ in range(x+1)]
        
        # Base case
        dp[0][0][0] = 1
        
        # Fill the table
        for i in range(x + 1):
            for j in range(y + 1):
                for k in range(z + 1):
                    if i == 0 and j == 0 and k == 0:
                        continue
                    
                    ways = 0
                    if i > 0:
                        ways += dp[i-1][j][k]
                    if j > 0:
                        ways += dp[i][j-1][k]
                    if k > 0:
                        ways += dp[i][j][k-1]
                    
                    dp[i][j][k] = ways
        
        return dp[x][y][z]
    
    def count_paths_with_weight_limit(grid, max_weight):
        """
        Count paths where total weight doesn't exceed limit
        Each cell has a weight, we want to count valid paths
        """
        m, n = len(grid), len(grid[0])
        
        # dp[i][j][w] = number of ways to reach (i,j) with total weight w
        dp = [[[0 for _ in range(max_weight + 1)] for _ in range(n)] for _ in range(m)]
        
        # Base case
        if grid[0][0] <= max_weight:
            dp[0][0][grid[0][0]] = 1
        
        # Fill first row
        for j in range(1, n):
            for w in range(max_weight + 1):
                if dp[0][j-1][w] > 0 and w + grid[0][j] <= max_weight:
                    dp[0][j][w + grid[0][j]] += dp[0][j-1][w]
        
        # Fill first column
        for i in range(1, m):
            for w in range(max_weight + 1):
                if dp[i-1][0][w] > 0 and w + grid[i][0] <= max_weight:
                    dp[i][0][w + grid[i][0]] += dp[i-1][0][w]
        
        # Fill the rest
        for i in range(1, m):
            for j in range(1, n):
                for w in range(max_weight + 1):
                    cell_weight = grid[i][j]
                    if w >= cell_weight:
                        prev_weight = w - cell_weight
                        # From above
                        dp[i][j][w] += dp[i-1][j][prev_weight]
                        # From left
                        dp[i][j][w] += dp[i][j-1][prev_weight]
        
        # Sum all valid weights at destination
        return sum(dp[m-1][n-1])

# Test 3D paths
result_3d = count_paths_3d(2, 2, 2)
print(f"Paths from (0,0,0) to (2,2,2): {result_3d}")

def count_ways_custom_steps(n, steps):
    """
    Count ways to climb n stairs with given step sizes
    
    Args:
        n: number of stairs
        steps: list of allowed step sizes
    
    Returns:
        number of ways to climb exactly n stairs
    """
    # Your implementation here
    pass

def count_ways_optimized(n, steps):
    """
    Space-optimized version (if possible)
    """
    # Your implementation here
    pass

# Test cases
test_cases = [
    (5, [1, 2]),        # Standard climbing stairs
    (4, [1, 3, 4]),     # Custom step sizes
    (6, [2, 3]),        # No single steps allowed
    (10, [1, 2, 3, 4, 5])  # Many step options
]

for n, steps in test_cases:
    result = count_ways_custom_steps(n, steps)
    print(f"n={n}, steps={steps}: {result} ways")

def count_ways_custom_steps(n, steps):
    if n == 0:
        return 1
    
    dp = [0] * (n + 1)
    dp[0] = 1
    
    for i in range(1, n + 1):
        for step in steps:
            if i >= step:
                dp[i] += dp[i - step]
    
    return dp[n]

def count_ways_optimized(n, steps):
    if not steps:
        return 0
    
    max_step = max(steps)
    if n == 0:
        return 1
    
    # Only keep last max_step values
    dp = [0] * min(n + 1, max_step + 1)
    dp[0] = 1
    
    for i in range(1, n + 1):
        current = 0
        for step in steps:
            if i >= step:
                idx = (i - step) % len(dp)
                current += dp[idx]
        
        dp[i % len(dp)] = current
    
    return dp[n % len(dp)]

# steps =  [0, 10, -5, 2, 8, -3, 1, 4]
# indices= [0, 1,  2,  3, 4,  5,  6, 7]
# One optimal path might be: 0 -> 1 -> 4 -> 7 (points: 0 + 10 + 8 + 4 = 22)

def max_points_climbing(points):
    """
    Find maximum points collecting while climbing stairs
    
    Args:
        points: list where points[i] is the point value of step i
    
    Returns:
        tuple: (max_points, optimal_path)
    """
    # Your implementation here
    pass

def reconstruct_path(dp, points, n):
    """
    Reconstruct the optimal path from DP table
    """
    # Your implementation here
    pass

def debug_step_counting():
    """
    Debugging techniques for step counting problems
    """
    
    def trace_dp_table(n, steps):
        """Print complete DP table for small problems"""
        dp = [0] * (n + 1)
        dp[0] = 1
        
        print(f"DP table for n={n}, steps={steps}")
        print(f"dp[0] = {dp[0]}")
        
        for i in range(1, n + 1):
            for step in steps:
                if i >= step:
                    dp[i] += dp[i - step]
            
            contributors = []
            for step in steps:
                if i >= step:
                    contributors.append(f"dp[{i-step}]={dp[i-step]}")
            
            print(f"dp[{i}] = {' + '.join(contributors)} = {dp[i]}")
        
        return dp[n]
    
    def validate_with_brute_force(n, steps, max_n=10):
        """Compare DP solution with brute force for small inputs"""
        if n > max_n:
            print(f"Skipping validation for n={n} (too large)")
            return
        
        def count_brute_force(remaining, current_steps):
            if remaining == 0:
                return 1
            if remaining < 0:
                return 0
            
            total = 0
            for step in current_steps:
                total += count_brute_force(remaining - step, current_steps)
            return total
        
        dp_result = count_ways_custom_steps(n, steps)
        bf_result = count_brute_force(n, steps)
        
        if dp_result == bf_result:
            print(f"✓ Validation passed: n={n}, steps={steps}, result={dp_result}")
        else:
            print(f"✗ Validation failed: n={n}, steps={steps}, DP={dp_result}, BF={bf_result}")

# Test debugging
trace_dp_table(5, [1, 2])
validate_with_brute_force(5, [1, 2])

def optimization_techniques():
    """
    Common optimization techniques for step counting
    """
    
    def space_optimization_analysis():
        """Analyze space optimization potential"""
        print("Space Optimization Guidelines:")
        print("1. If only need previous k values, use rolling array of size k")
        print("2. For 2D grids, often can reduce to 1D by processing row by row")
        print("3. For constraints, sometimes can use bitmasking to compress state")
    
    def time_optimization_tips():
        """Time complexity optimization strategies"""
        print("Time Optimization Tips:")
        print("1. Precompute frequently used values")
        print("2. Use mathematical formulas when possible (e.g., combinations)")
        print("3. Consider matrix exponentiation for large n with small step sizes")
        print("4. Use memoization to avoid recomputation in recursive solutions")

optimization_techniques()

def professional_step_counting_template():
    """
    Professional template for step counting problems
    """
    
    class StepCountingSolver:
        def __init__(self, allowed_steps=None):
            self.allowed_steps = allowed_steps or [1, 2]
            self.memo = {}
        
        def count_ways(self, n, use_memoization=False):
            """
            Count ways to climb n steps
            
            Args:
                n: target position
                use_memoization: whether to use top-down approach
            
            Returns:
                number of ways to reach position n
            """
            if use_memoization:
                return self._count_ways_memo(n)
            else:
                return self._count_ways_tabulation(n)
        
        def _count_ways_memo(self, n):
            """Memoized recursive solution"""
            if n in self.memo:
                return self.memo[n]
            
            if n == 0:
                return 1
            if n < 0:
                return 0
            
            ways = 0
            for step in self.allowed_steps:
                ways += self._count_ways_memo(n - step)
            
            self.memo[n] = ways
            return ways
        
        def _count_ways_tabulation(self, n):
            """Bottom-up tabulation solution"""
            if n == 0:
                return 1
            
            dp = [0] * (n + 1)
            dp[0] = 1
            
            for i in range(1, n + 1):
                for step in self.allowed_steps:
                    if i >= step:
                        dp[i] += dp[i - step]
            
            return dp[n]
        
        def find_optimal_path(self, values, objective='max'):
            """
            Find optimal path with given objective
            
            Args:
                values: list of values at each position
                objective: 'max' for maximum value, 'min' for minimum
            
            Returns:
                tuple: (optimal_value, path)
            """
            n = len(values) - 1
            dp = [-float('inf')] * (n + 1) if objective == 'max' else [float('inf')] * (n + 1)
            parent = [-1] * (n + 1)
            
            dp[0] = values[0]
            
            for i in range(1, n + 1):
                for step in self.allowed_steps:
                    if i >= step:
                        new_value = dp[i - step] + values[i]
                        
                        if objective == 'max' and new_value > dp[i]:
                            dp[i] = new_value
                            parent[i] = i - step
                        elif objective == 'min' and new_value < dp[i]:
                            dp[i] = new_value
                            parent[i] = i - step
            
            # Reconstruct path
            path = []
            current = n
            while current != -1:
                path.append(current)
                current = parent[current]
            path.reverse()
            
            return dp[n], path

# Usage example
solver = StepCountingSolver([1, 2, 3])
ways = solver.count_ways(10)
print(f"Ways to climb 10 stairs: {ways}")

values = [0, 1, -2, 3, 1, -1, 4, 2]
optimal_value, path = solver.find_optimal_path(values, 'max')
print(f"Optimal path: {path}, value: {optimal_value}")

def code_organization_best_practices():
    """
    Best practices for organizing step counting code
    """
    
    guidelines = {
        "Function Design": [
            "Separate counting logic from path reconstruction",
            "Use clear parameter names (n for position, steps for allowed moves)",
            "Include comprehensive docstrings with examples",
            "Handle edge cases explicitly at function start"
        ],
        
        "State Representation": [
            "Choose minimal but complete state representation",
            "Consider space-time tradeoffs in state design",
            "Document what each state dimension represents",
            "Use meaningful variable names for DP arrays"
        ],
        
        "Testing Strategy": [
            "Test with small examples you can verify manually",
            "Include edge cases (n=0, n=1, empty step arrays)",
            "Compare optimized versions with unoptimized for correctness",
            "Validate with brute force for small inputs"
        ],
        
        "Performance Considerations": [
            "Profile code to identify bottlenecks",
            "Consider space optimization only after correctness",
            "Use appropriate data structures for the problem size",
            "Document time and space complexity clearly"
        ]
    }
    
    for category, tips in guidelines.items():
        print(f"\n{category}:")
        for tip in tips:
            print(f"  • {tip}")

code_organization_best_practices()